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:
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.length1 <= n, m <= 500startPos.length == 20 <= startrow, startcol < ns consists of 'L', 'R', 'U', and 'D'.Problem Overview: You control a robot on an n x n grid starting at position (row, col). A string of instructions (L, R, U, D) moves the robot one cell at a time. For every suffix of the instruction string, compute how many moves the robot can execute before it leaves the grid.
Approach 1: Simulation for Each Starting Instruction (O(m²) time, O(1) space)
The direct approach runs a fresh simulation for every suffix. For index i, reset the robot to the starting cell and iterate through instructions s[i...]. Update the current position for each character and stop once the position falls outside the grid bounds. The number of successful moves becomes the answer for that suffix. This method relies purely on step‑by‑step movement checks and simple boundary validation, making it easy to implement using basic loops. The downside is repeated work: many suffixes simulate nearly identical instruction sequences, which pushes the worst‑case runtime to O(m²) where m is the instruction length.
Approach 2: Precomputing and Reverse Simulation (O(m) time, O(m) space)
An optimized solution avoids repeating full simulations. Track the robot's relative displacement from the starting point while processing instructions from right to left. Maintain prefix bounds for how far the robot can move horizontally and vertically without leaving the grid. Each instruction changes the displacement (dx, dy), and you update the allowed range based on grid limits and the start position. When the displacement exceeds the allowed window, the suffix cannot extend further. By updating these ranges incrementally, you reuse information from previously processed suffixes instead of re-simulating moves. The entire instruction string is processed once, giving O(m) time.
Both solutions rely on straightforward movement logic often seen in simulation problems and character iteration patterns common in string processing tasks. The optimized method adds prefix-style range tracking to avoid repeated work.
Recommended for interviews: Start with the simulation approach to demonstrate correct reasoning about grid boundaries and instruction handling. Then discuss the reverse precomputation optimization. Interviewers typically expect recognition that naive simulation repeats work and that suffix results can be derived incrementally for an O(m) solution.
This approach involves simulating the robot's moves starting from each instruction, checking if the robot stays within bounds of the grid. For each starting instruction, follow the operations one by one and update the robot's position accordingly, ensuring the position remains valid.
The solution iterates over each starting point in the instruction string. It simulates the movement of the robot using loops while checking the boundary conditions at each step. If at any point the robot moves outside the grid, the simulation for that start point stops and the count is stored in the result array.
Time Complexity: O(m^2), where m is the length of the instruction string, as each starting position requires checking over subsequent instructions.
Space Complexity: O(1) additional space besides the output.
Instead of simulating each path naively, another approach tackles the problem in reverse. By precomputing the effect of reversing each instruction and stopping at grid limits, we can gradually build up the result array.
The C program back-calculates from the end of the instruction string, storing lengths of valid paths in a backward manner to eventually obtain all initially possible move counts.
Time Complexity: O(m^2), as each position from the end checks forward.
Space Complexity: O(1) besides output storage.
| Approach | Complexity |
|---|---|
| Simulation for Each Starting Instruction | Time Complexity: O(m^2), where m is the length of the instruction string, as each starting position requires checking over subsequent instructions. |
| Precomputing and Reverse Simulation | Time Complexity: O(m^2), as each position from the end checks forward. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulation for Each Starting Instruction | O(m²) | O(1) | Best for quick implementation and understanding the movement logic |
| Precomputing and Reverse Simulation | O(m) | O(m) | Preferred for large instruction strings where repeated simulation is expensive |
Execution of All Suffix Instructions Staying in a Grid | Leetcode 2120 | Contest 273 | Easy Peasy • Coding Decoded • 1,453 views views
Watch 5 more video solutions →Practice Execution of All Suffix Instructions Staying in a Grid with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor