Watch 6 video solutions for Execution of All Suffix Instructions Staying in a Grid, a medium level problem involving String, Simulation. This walkthrough by Coding Decoded has 1,453 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |