LeetCode 2120 - Execution of All Suffix Instructions Staying in a Grid

The problem asks us to simulate a robot moving on an n x n grid, starting from a specified position startPos = [startrow, startcol].

leetcodemediumstringsimulation

LeetCode Problem 2120

Difficulty: 🟡 Medium
Topics: String, Simulation

Solution

Problem Understanding

The problem asks us to simulate a robot moving on an n x n grid, starting from a specified position startPos = [startrow, startcol]. We are given a sequence of movement instructions as a string s, where each character represents a direction: 'L' for left, 'R' for right, 'U' for up, and 'D' for down. The robot can start executing the instructions from any index i of the string s and continues sequentially until either the next move would take it off the grid or it reaches the end of the instruction string.

The output is an array answer of length m (length of s) where answer[i] records the number of instructions the robot can execute if it starts at the ith instruction. For instance, if the robot begins at instruction i and immediately tries to move off the grid, answer[i] should be 0.

Constraints indicate that the grid and instruction string are relatively small (n, m <= 500), which allows an O(m^2) simulation approach but may not efficiently scale beyond that. Important edge cases include situations where the robot starts at a boundary, or the grid is minimal (n = 1), in which case any move is invalid.

Approaches

Brute Force

A naive approach is to simulate starting from each instruction i. For each i, initialize the robot's position at startPos and simulate moving step by step until the robot either exits the grid or the instructions end. Count the number of moves executed and store it in answer[i]. This is correct because it directly follows the problem’s rules, but it is inefficient because for each starting index, it may simulate up to m moves. In the worst case, this gives O(m^2) time complexity.

Optimized Approach

The main insight for optimization is that we can simulate all suffix instructions sequentially while tracking the robot’s position. For each suffix, we can iterate until the robot goes off the grid. Since the grid size is small (n <= 500) and instructions are also limited (m <= 500), we can still safely implement this direct simulation. More advanced approaches, like precomputing valid moves for each direction using dynamic programming or segment trees, are unnecessary due to the constraints.

Approach Time Complexity Space Complexity Notes
Brute Force O(m^2) O(m) Simulate each suffix individually
Optimized O(m^2) O(m) Same as brute force here due to constraint limits, can stop simulation early if robot goes off-grid

Algorithm Walkthrough

  1. Initialize an array answer of length m with zeros.
  2. Iterate over each index i from 0 to m - 1. This represents the starting instruction.
  3. For each i, initialize the robot’s position at startrow, startcol.
  4. Initialize a counter steps to 0.
  5. Iterate from index j = i to m - 1:
  • Check the instruction s[j].
  • Update the robot’s position based on the instruction: decrement row for 'U', increment row for 'D', decrement column for 'L', increment column for 'R'.
  • If the robot moves off the grid (row or column < 0 or ≥ n), break the loop.
  • Otherwise, increment steps.
  1. Store steps in answer[i].
  2. After processing all starting indices, return answer.

Why it works: The algorithm directly follows the problem's rules, iterating over each suffix of instructions and counting valid moves until the robot exits the grid. Since all moves are simulated correctly and independently, the result is accurate for each starting index.

Python Solution

from typing import List

class Solution:
    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:
        answer = [0] * len(s)
        directions = {'U': (-1, 0), 'D': (1, 0), 'L': (0, -1), 'R': (0, 1)}
        
        for i in range(len(s)):
            x, y = startPos
            steps = 0
            for j in range(i, len(s)):
                dx, dy = directions[s[j]]
                x_new, y_new = x + dx, y + dy
                if 0 <= x_new < n and 0 <= y_new < n:
                    x, y = x_new, y_new
                    steps += 1
                else:
                    break
            answer[i] = steps
        
        return answer

This implementation initializes a dictionary to map directions to coordinate changes. For each starting index, it simulates moves until the robot goes off-grid, incrementing a counter. The loop breaks immediately upon hitting a boundary, ensuring efficiency.

Go Solution

func executeInstructions(n int, startPos []int, s string) []int {
    m := len(s)
    answer := make([]int, m)
    directions := map[byte][2]int{
        'U': {-1, 0},
        'D': {1, 0},
        'L': {0, -1},
        'R': {0, 1},
    }

    for i := 0; i < m; i++ {
        x, y := startPos[0], startPos[1]
        steps := 0
        for j := i; j < m; j++ {
            dx, dy := directions[s[j]][0], directions[s[j]][1]
            xNew, yNew := x+dx, y+dy
            if xNew >= 0 && xNew < n && yNew >= 0 && yNew < n {
                x, y = xNew, yNew
                steps++
            } else {
                break
            }
        }
        answer[i] = steps
    }

    return answer
}

The Go implementation is almost identical in logic. The main difference is type handling: Go uses byte for string indexing and arrays for the direction mapping. Slices handle dynamic arrays and no explicit memory allocation for answer beyond initialization.

Worked Examples

Example 1

Input: n = 3, startPos = [0,1], s = "RRDDLU"

i Instructions Robot Positions Steps answer[i]
0 RRDDLU (0,1) -> (0,2) -> out 1 1
1 RDDLU (0,1) -> (0,2) -> (1,2) -> (2,2) -> (2,1) -> (1,1) 5 5
2 DDLU (0,1) -> (1,1) -> (2,1) -> (2,0) -> (1,0) 4 4
3 DLU (0,1) -> (1,1) -> (1,0) -> (0,0) 3 3
4 LU (0,1) -> (0,0) -> out 1 1
5 U (0,1) -> out 0 0

Output: [1,5,4,3,1,0]

Complexity Analysis

Measure Complexity Explanation
Time O(m^2) For each starting instruction, we may iterate through all remaining instructions. With m <= 500, this is acceptable.
Space O(m) Storing the answer array of length m. Direction dictionary uses constant space.

The time complexity is quadratic in the length of the instruction string, but since the constraints limit m to 500, the solution executes efficiently within typical LeetCode limits.

Test Cases

# Provided examples
assert Solution().executeInstructions(3, [0,1], "RRDDLU") == [1,5,4,3,1,0]
assert Solution().executeInstructions(2, [1,1], "LURD") == [4,1,0,0]
assert Solution().executeInstructions(1, [0,0], "LRUD") == [0,0,0,0]

# Boundary cases
assert Solution().executeInstructions(1, [0,0], "") == []  # empty instructions
assert Solution().executeInstructions(500, [0,0], "R"*500) == [499-i for i in range(500)]  # long row moves

# Robot starting at corner
assert Solution().executeInstructions(3, [2,2], "LLUU") == [2,1,0,0]

# All moves valid
assert Solution().executeInstructions(3, [1,1], "UDLR") == [4,3,2,1]
Test Why
Empty instruction string Ensures algorithm handles zero-length input
Maximum length moves Tests scalability and correctness of counting
Robot starting at corner Validates boundary handling
All moves valid Checks robot executes all moves without early termination

Edge