Introduction

In this blog post, we will explore how to solve the LeetCode problem "2120" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

There is an n x n grid, with the top-left cell at (0, 0) and the bottom-right cell at (n - 1, n - 1). You are given the integer n and an integer array startPos where startPos = [startrow, startcol] indicates that a robot is initially at cell (startrow, startcol). You are also given a 0-indexed string s of length m where s[i] is the ith instruction for the robot: 'L' (move left), 'R' (move right), 'U' (move up), and 'D' (move down). The robot can begin executing from any ith instruction in s. It executes the instructions one by one towards the end of s but it stops if either of these conditions is met: The next instruction will move the robot off the grid. There are no more instructions left to execute. Return an array answer of length m where answer[i] is the number of instructions the robot can execute if the robot begins executing from the ith instruction in s. Example 1: Input: n = 3, startPos = [0,1], s = "RRDDLU" Output: [1,5,4,3,1,0] Explanation: Starting from startPos and beginning execution from the ith instruction: - 0th: "RRDDLU". Only one instruction "R" can be executed before it moves off the grid. - 1st: "RDDLU". All five instructions can be executed while it stays in the grid and ends at (1, 1). - 2nd: "DDLU". All four instructions can be executed while it stays in the grid and ends at (1, 0). - 3rd: "DLU". All three instructions can be executed while it stays in the grid and ends at (0, 0). - 4th: "LU". Only one instruction "L" can be executed before it moves off the grid. - 5th: "U". If moving up, it would move off the grid. Example 2: Input: n = 2, startPos = [1,1], s = "LURD" Output: [4,1,0,0] Explanation: - 0th: "LURD". - 1st: "URD". - 2nd: "RD". - 3rd: "D". Example 3: Input: n = 1, startPos = [0,0], s = "LRUD" Output: [0,0,0,0] Explanation: No matter which instruction the robot begins execution from, it would move off the grid. Constraints: m == s.length 1 <= n, m <= 500 startPos.length == 2 0 <= startrow, startcol < n s consists of 'L', 'R', 'U', and 'D'.

Explanation

• Iterate through the string s from index 0 to m-1. For each starting index i, simulate the robot's movement based on the subsequent instructions.
  • Keep track of the current position of the robot and the number of instructions executed.
  • Terminate the simulation when the robot moves off the grid or when all instructions have been executed from the current starting index.

• Runtime Complexity: O(m*m), where m is the length of the string s. Storage Complexity: O(m) for the answer array.

Code

    def executeInstructions(n: int, startPos: list[int], s: str) -> list[int]:
    """
    Calculates the number of instructions a robot can execute starting from each index of a string,
    given a grid size and initial position.

    Args:
        n: The size of the n x n grid.
        startPos: The initial position of the robot [startrow, startcol].
        s: A string of instructions ('L', 'R', 'U', 'D').

    Returns:
        A list of integers, where each element represents the number of instructions the robot can execute
        starting from the corresponding index in the input string.
    """

    m = len(s)
    answer = []

    for i in range(m):
        row, col = startPos[0], startPos[1]
        count = 0
        for j in range(i, m):
            if s[j] == 'R':
                col += 1
            elif s[j] == 'L':
                col -= 1
            elif s[j] == 'U':
                row -= 1
            else:  # s[j] == 'D'
                row += 1

            if not (0 <= row < n and 0 <= col < n):
                break

            count += 1
        answer.append(count)

    return answer