#2120

Medium

LeetCode Problem Workspace

Execution of All Suffix Instructions Staying in a Grid

Simulate robot moves from every instruction index on an n x n grid, counting valid steps without leaving boundaries.

Problem Statement

You are given an n x n grid with coordinates from (0,0) to (n-1,n-1). A robot starts at startPos = [startrow, startcol] and follows a series of movement instructions given in a string s, where each character is 'L', 'R', 'U', or 'D'.

For every index i in s, the robot starts executing the instructions from s[i] to the end of s. Count the number of consecutive moves executed without the robot leaving the grid. Return an array where the ith element represents this count for the ith starting index.

Examples

Example 1

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

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

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]

0th: "LURD".
1st: "URD".
2nd: "RD".
3rd: "D".

Example 3

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

Output: [0,0,0,0]

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'.

Solution Approach

Direct Simulation from Each Suffix

Iterate over each index i in s and simulate moves starting at startPos. Increment a counter until a move would take the robot off the grid, then record the count in the result array.

Optimize with Early Stopping

For each suffix, stop simulation immediately when a boundary is reached. This avoids unnecessary processing of remaining moves and maintains O(n*m) complexity within constraints.

Use Coordinate Updates Instead of Strings

Map each instruction to a coordinate delta. Apply delta updates directly to row and column for faster execution and clearer handling of grid boundaries.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(m*n) because each of the m suffixes may simulate up to n moves in the worst case. Space complexity is O(m) for storing results.

What Interviewers Usually Probe

Checks if you notice simulation is feasible given small constraints.
Looks for handling edge cases when the robot is at a grid boundary.
Evaluates if the approach efficiently stops at invalid moves.

Common Pitfalls or Variants

Common pitfalls

Not stopping immediately when a move goes off the grid, leading to incorrect counts.
Incorrectly updating coordinates causing off-by-one errors.
Confusing the starting index with the overall string length when iterating suffixes.

Follow-up variants

Simulate instructions on a non-square grid or rectangular grid.
Count moves until a specific target cell is reached instead of leaving the grid.
Allow diagonal moves and adapt the delta updates accordingly.

FAQ

What is the main pattern in Execution of All Suffix Instructions Staying in a Grid?

The problem follows a String plus Simulation pattern, simulating each suffix of instructions and counting moves within grid boundaries.

Can we optimize beyond simulating each instruction?

Given the constraints (n, m <= 500), direct simulation with early stopping is efficient enough; further optimizations are not necessary.

How do we handle the robot at the edge of the grid?

Stop simulation immediately when the next move would leave the grid to prevent counting invalid steps.

What data structure is best for representing moves?

Use simple coordinate deltas (row, col) for 'L', 'R', 'U', 'D'; arrays or maps work well for clarity and speed.

Why do we need to simulate from each instruction index?

Because each suffix starting point can have a different number of valid moves before the robot leaves the grid, requiring separate simulation counts.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:
        ans = []
        m = len(s)
        mp = {"L": [0, -1], "R": [0, 1], "U": [-1, 0], "D": [1, 0]}
        for i in range(m):
            x, y = startPos
            t = 0
            for j in range(i, m):
                a, b = mp[s[j]]
                if 0 <= x + a < n and 0 <= y + b < n:
                    x, y, t = x + a, y + b, t + 1
                else:
                    break
            ans.append(t)
        return ans

Continue Practicing

#2109 adding spaces to a string #2138 divide a string into groups of size k #2075 decode the slanted ciphertext