Execution of All Suffix Instructions Staying in a Grid solution and explanation
6 more videos on this problem
Execution of All Suffix Instructions Staying in a Grid | Leetcode 2120 | Contest 273 | Easy PeasyCoding Decoded · 7:28 · 1K views
2120. Execution of All Suffix Instructions Staying in a Grid (Leetcode Medium)Programming Live with Larry · 8:18 · 638 views
Leetcode Weekly Contest 273 | Problem 2119 , 2120 , 2121 | CONSTRUCTIVE ALGO | CODE EXPLAINERcode Explainer · 21:08 · 516 views
Execution of All Suffix Instructions Staying in a Grid | LeetCode | Weekly Contest 273 | SolutionsWe are Coders · 4:35 · 405 views
Execution of All Suffix Instructions Staying in a Grid (Leetcode Weekly 273)Soumya Bhattacharjee · 2:10 · 198 views
2120. Execution of All Suffix Instructions .. || Weekly Contest 273 Solve || LEETCODE || BanglaHAPHAZARD · 13:45 · 113 views
LeetCode 2120: Execution of All Suffix Instructions Staying in a GridAlitaCode · 28:59 · 8 views
The problem
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.length1 <= n, m <= 500startPos.length == 20 <= startrow, startcol < nsconsists 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.
def executeInstructions(n, startPos, s):
m = len(s)
answer = []
for i in range(m):
row, col = startPos
count = 0
for j in range(i, m):
if s[j] == 'L':
col -= 1
elif s[j] == 'R':
col += 1
elif s[j] == 'U':
row -= 1
elif s[j] == 'D':
row += 1
if row < 0 or row >= n or col < 0 or col >= n:
break
count += 1
answer.append(count)
return answer
n = 3
startPos = [0, 1]
s = "RRDDLU"
print(executeInstructions(n, startPos, s))import java.util.Arrays;
public class RobotGrid {
public static int[] executeInstructions(int n, int[] startPos, String s) {
int m = s.length();
int[] answer = new int[m];
for (int i = 0; i < m; i++) {
int row = startPos[0], col = startPos[1];
int count = 0;
for (int j = i; j < m; j++) {
char instruction = s.charAt(j);
if (instruction == 'L') col--;
else if (instruction == 'R') col++;
else if (instruction == 'U') row--;
else if (instruction == 'D') row++;
if (row < 0 || row >= n || col < 0 || col >= n) break;
count++;
}
answer[i] = count;
}
return answer;
}
public static void main(String[] args) {
int[] startPos = {0, 1};
String s = "RRDDLU";
int[] result = executeInstructions(3, startPos, s);
System.out.println(Arrays.toString(result));
}
}#include <vector>
#include <string>
#include <iostream>
std::vector<int> executeInstructions(int n, std::vector<int>& startPos, std::string s) {
int m = s.size();
std::vector<int> answer(m, 0);
for (int i = 0; i < m; ++i) {
int row = startPos[0];
int col = startPos[1];
int count = 0;
for (int j = i; j < m; ++j) {
if (s[j] == 'L') --col;
else if (s[j] == 'R') ++col;
else if (s[j] == 'U') --row;
else if (s[j] == 'D') ++row;
if (row < 0 || row >= n || col < 0 || col >= n) break;
count++;
}
answer[i] = count;
}
return answer;
}
int main() {
std::vector<int> startPos = {0, 1};
std::string s = "RRDDLU";
std::vector<int> result = executeInstructions(3, startPos, s);
for (int res : result) {
std::cout << res << " ";
}
return 0;
}function executeInstructions(n, startPos, s) {
const m = s.length;
const answer = Array(m).fill(0);
for (let i = 0; i < m; i++) {
let row = startPos[0], col = startPos[1];
let count = 0;
for (let j = i; j < m; j++) {
if (s[j] === 'L') col--;
else if (s[j] === 'R') col++;
else if (s[j] === 'U') row--;
else if (s[j] === 'D') row++;
if (row < 0 || row >= n || col < 0 || col >= n) break;
count++;
}
answer[i] = count;
}
return answer;
}
const n = 3;
const startPos = [0, 1];
const s = "RRDDLU";
console.log(executeInstructions(n, startPos, s));#include <stdio.h>
#include <string.h>
void executeInstructions(int n, int* startPos, char* s, int m, int* answer) {
for (int i = 0; i < m; i++) {
int row = startPos[0];
int col = startPos[1];
int count = 0;
for (int j = i; j < m; j++) {
char instruction = s[j];
if (instruction == 'L') col--;
else if (instruction == 'R') col++;
else if (instruction == 'U') row--;
else if (instruction == 'D') row++;
if (row < 0 || row >= n || col < 0 || col >= n) break;
count++;
}
answer[i] = count;
}
}
int main() {
int startPos[] = {0, 1};
char s[] = "RRDDLU";
int m = strlen(s);
int answer[m];
executeInstructions(3, startPos, s, m, answer);
for (int i = 0; i < m; i++) {
printf("%d ", answer[i]);
}
return 0;
}using System;
public class RobotGrid {
public static int[] ExecuteInstructions(int n, int[] startPos, string s) {
int m = s.Length;
int[] answer = new int[m];
for (int i = 0; i < m; i++) {
int row = startPos[0], col = startPos[1];
int count = 0;
for (int j = i; j < m; j++) {
char instruction = s[j];
if (instruction == 'L') col--;
else if (instruction == 'R') col++;
else if (instruction == 'U') row--;
else if (instruction == 'D') row++;
if (row < 0 || row >= n || col < 0 || col >= n) break;
count++;
}
answer[i] = count;
}
return answer;
}
public static void Main(string[] args) {
int[] startPos = {0, 1};
string s = "RRDDLU";
int[] result = ExecuteInstructions(3, startPos, s);
Console.WriteLine(string.Join(" ", result));
}
}The Python version directly applies the idea of simulating the robot’s trajectory on the grid for each potential starting command. It keeps track of the number of valid moves before the robot hits the boundary.
Time Complexity: O(m^2).
Space Complexity: O(m) for the result list.
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.
def executeInstructions(n, startPos, s):
m = len(s)
answer = [0] * m
for i in range(m-1, -1, -1):
count = 0 if i == m - 1 else answer[i + 1]
row, col = startPos
for j in range(i, m):
if s[j] == 'L':
col -= 1
elif s[j] == 'R':
col += 1
elif s[j] == 'U':
row -= 1
elif s[j] == 'D':
row += 1
if row < 0 or row >= n or col < 0 or col >= n:
break
count += 1
answer[i] = count
return answer
n = 3
startPos = [0, 1]
s = "RRDDLU"
print(executeInstructions(n, startPos, s))import java.util.Arrays;
public class RobotGrid {
public static int[] executeInstructions(int n, int[] startPos, String s) {
int m = s.length();
int[] answer = new int[m];
for (int i = m - 1; i >= 0; i--) {
int count = (i == m - 1) ? 0 : answer[i + 1];
int row = startPos[0], col = startPos[1];
for (int j = i; j < m; j++) {
char instruction = s.charAt(j);
if (instruction == 'L') col--;
else if (instruction == 'R') col++;
else if (instruction == 'U') row--;
else if (instruction == 'D') row++;
if (row < 0 || row >= n || col < 0 || col >= n) break;
count++;
}
answer[i] = count;
}
return answer;
}
public static void main(String[] args) {
int[] startPos = {0, 1};
String s = "RRDDLU";
int[] result = executeInstructions(3, startPos, s);
System.out.println(Arrays.toString(result));
}
}#include <vector>
#include <string>
#include <iostream>
std::vector<int> executeInstructions(int n, std::vector<int>& startPos, std::string s) {
int m = s.size();
std::vector<int> answer(m, 0);
for (int i = m - 1; i >= 0; --i) {
int count = (i == m - 1) ? 0 : answer[i + 1];
int row = startPos[0], col = startPos[1];
for (int j = i; j < m; j++) {
if (s[j] == 'L') --col;
else if (s[j] == 'R') ++col;
else if (s[j] == 'U') --row;
else if (s[j] == 'D') ++row;
if (row < 0 || row >= n || col < 0 || col >= n) break;
count++;
}
answer[i] = count;
}
return answer;
}
int main() {
std::vector<int> startPos = {0, 1};
std::string s = "RRDDLU";
std::vector<int> result = executeInstructions(3, startPos, s);
for (int res : result) {
std::cout << res << " ";
}
return 0;
}function executeInstructions(n, startPos, s) {
const m = s.length;
const answer = Array(m).fill(0);
for (let i = m - 1; i >= 0; i--) {
let count = (i == m - 1) ? 0 : answer[i + 1];
let row = startPos[0], col = startPos[1];
for (let j = i; j < m; j++) {
if (s[j] === 'L') col--;
else if (s[j] === 'R') col++;
else if (s[j] === 'U') row--;
else if (s[j] === 'D') row++;
if (row < 0 || row >= n || col < 0 || col >= n) break;
count++;
}
answer[i] = count;
}
return answer;
}
const n = 3;
const startPos = [0, 1];
const s = "RRDDLU";
console.log(executeInstructions(n, startPos, s));#include <stdio.h>
#include <string.h>
void executeInstructions(int n, int* startPos, char* s, int m, int* answer) {
int count;
int row_curr, col_curr;
for (int i = m - 1; i >= 0; i--) {
count = (i == m - 1) ? 0 : answer[i + 1];
row_curr = startPos[0], col_curr = startPos[1];
for (int j = i; j < m; j++) {
if (s[j] == 'L') col_curr--;
else if (s[j] == 'R') col_curr++;
else if (s[j] == 'U') row_curr--;
else if (s[j] == 'D') row_curr++;
if (row_curr < 0 || row_curr >= n || col_curr < 0 || col_curr >= n) break;
count++;
}
answer[i] = count;
}
}
int main() {
int startPos[] = {0, 1};
char s[] = "RRDDLU";
int m = strlen(s);
int answer[m];
executeInstructions(3, startPos, s, m, answer);
for (int i = 0; i < m; i++) {
printf("%d ", answer[i]);
}
return 0;
}using System;
public class RobotGrid {
public static int[] ExecuteInstructions(int n, int[] startPos, string s) {
int m = s.Length;
int[] answer = new int[m];
for (int i = m - 1; i >= 0; i--) {
int count = (i == m - 1) ? 0 : answer[i + 1];
int row = startPos[0], col = startPos[1];
for (int j = i; j < m; j++) {
char instruction = s[j];
if (instruction == 'L') col--;
else if (instruction == 'R') col++;
else if (instruction == 'U') row--;
else if (instruction == 'D') row++;
if (row < 0 || row >= n || col < 0 || col >= n) break;
count++;
}
answer[i] = count;
}
return answer;
}
public static void Main(string[] args) {
int[] startPos = {0, 1};
string s = "RRDDLU";
int[] result = ExecuteInstructions(3, startPos, s);
Console.WriteLine(string.Join(" ", result));
}
}Python code executes reverse processing from the end of instruction string towards the start, accumulating valid step counts in contrast.
Time Complexity: O(m^2).
Space Complexity: O(m) for answer list.
Approach 3: Default Approach
function executeInstructions(n: number, startPos: number[], s: string): number[] {
const m = s.length;
const ans = new Array(m);
for (let i = 0; i < m; i++) {
let [y, x] = startPos;
let j: number;
for (j = i; j < m; j++) {
const c = s[j];
if (c === 'U') {
y--;
} else if (c === 'D') {
y++;
} else if (c === 'L') {
x--;
} else {
x++;
}
if (y === -1 || y === n || x === -1 || x === n) {
break;
}
}
ans[i] = j - i;
}
return ans;
}func executeInstructions(n int, startPos []int, s string) []int {
m := len(s)
mp := make(map[byte][]int)
mp['L'] = []int{0, -1}
mp['R'] = []int{0, 1}
mp['U'] = []int{-1, 0}
mp['D'] = []int{1, 0}
ans := make([]int, m)
for i := 0; i < m; i++ {
x, y := startPos[0], startPos[1]
t := 0
for j := i; j < m; j++ {
a, b := mp[s[j]][0], mp[s[j]][1]
if 0 <= x+a && x+a < n && 0 <= y+b && y+b < n {
x += a
y += b
t++
} else {
break
}
}
ans[i] = t
}
return ans
}impl Solution {
pub fn execute_instructions(n: i32, start_pos: Vec<i32>, s: String) -> Vec<i32> {
let s = s.as_bytes();
let m = s.len();
let mut ans = vec![0; m];
for i in 0..m {
let mut y = start_pos[0];
let mut x = start_pos[1];
let mut j = i;
while j < m {
match s[j] {
b'U' => {
y -= 1;
}
b'D' => {
y += 1;
}
b'L' => {
x -= 1;
}
_ => {
x += 1;
}
}
if y == -1 || y == n || x == -1 || x == n {
break;
}
j += 1;
}
ans[i] = (j - i) as i32;
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Simulation for Each Starting Instruction | Time Complexity: O(m^2). |
| Precomputing and Reverse Simulation | Time Complexity: O(m^2). |
| Default Approach | – |
Complexity analysis
| 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 |
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.