Skip to main content
Talentd

Execution of All Suffix Instructions Staying in a Grid - Solution & Explanation

MediumStringSimulation17 min read
Practice this problem

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

Approach Overview

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 1: Simulation for Each Starting Instruction

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Precomputing and Reverse Simulation

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m^2), as each position from the end checks forward.
Space Complexity: O(1) besides output storage.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScriptRustC

Python

Java

C++

Go

TypeScript

Rust

C

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(1) additional space besides the output.

Precomputing and Reverse Simulation

Time Complexity: O(m^2), as each position from the end checks forward.
Space Complexity: O(1) besides output storage.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Simulation for Each Starting InstructionO(m²)O(1)Best for quick implementation and understanding the movement logic
Precomputing and Reverse SimulationO(m)O(m)Preferred for large instruction strings where repeated simulation is expensive

Video Solution

Execution of All Suffix Instructions Staying in a Grid | Leetcode 2120 | Contest 273 | Easy Peasy • Coding Decoded • 1,482 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Execution of All Suffix Instructions Staying in a Grid easy or hard?
The problem is rated Medium. The brute-force simulation is straightforward, but recognizing how to avoid repeated work across suffixes requires stronger algorithmic insight and careful boundary tracking.
Execution of All Suffix Instructions Staying in a Grid Python/Java solution
Python and Java implementations typically simulate robot movement using row and column variables updated for each instruction. The brute-force version loops through each suffix, while the optimized version maintains displacement ranges and computes results in linear time.
How to solve Execution of All Suffix Instructions Staying in a Grid in O(n)?
Process the instruction string in reverse while tracking cumulative displacement and valid movement bounds relative to the grid. Each step updates the allowable horizontal and vertical ranges based on the grid size and starting position. This avoids re-simulating each suffix and computes results in linear time.
What is the best approach for Execution of All Suffix Instructions Staying in a Grid?
The most efficient approach uses reverse processing with precomputed displacement bounds. By scanning the instruction string from right to left and maintaining valid movement ranges, each suffix result can be derived without re-running the full simulation. This reduces the complexity to O(m) time compared to the O(m^2) brute-force simulation.
Is Execution of All Suffix Instructions Staying in a Grid asked at Google/Amazon/Meta?
Grid movement and simulation problems appear frequently in interviews at companies like Amazon, Google, and Meta. Variations of this problem test reasoning about boundaries, incremental computation, and efficient handling of repeated simulations.
What data structure is used in Execution of All Suffix Instructions Staying in a Grid?
The solution mainly uses arrays or lists to store the result for each suffix. The logic itself relies on simple coordinate tracking and displacement calculations rather than complex data structures.
What is the time complexity of Execution of All Suffix Instructions Staying in a Grid?
The straightforward simulation approach runs in O(m^2) time because each suffix may simulate up to m moves. An optimized reverse precomputation method processes the instruction string once and runs in O(m) time with O(m) additional space.

Ready to solve this problem?

Practice Execution of All Suffix Instructions Staying in a Grid with our built-in code editor and test cases.

Practice on FleetCode
Previous

Out of Boundary Paths

Next

Robot Return to Origin