Execution of All Suffix Instructions Staying in a Grid

Execution of All Suffix Instructions Staying in a Grid - Problem

String Simulation Medium

There is an n × 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.

Input & Output

Example 1 — Basic Grid Navigation

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

› Output: [4,1,3,2,0,0]

💡 Note: Starting from index 0: RRDDLU executes R→[0,2], R→[0,3] (would go out), stops. Wait, let me recalculate: R→[0,2], R→can't go to [0,3] as it's out of bounds. Actually: R→[0,2], R→would go to [0,3] but that's out of 3x3 grid, so only 1 step. Let me recalculate all: Index 0: R→[0,2], R→would exit, so 1 step. Actually the grid is 0 to n-1, so [0,2] is valid in 3x3. R→[0,2] ✓, R→[0,3] ✗ (out of bounds). So 1 step from index 0.

Example 2 — Smaller Grid

$ Input: n = 2, startPos = [1,1], s = "LURD"

› Output: [4,1,1,1]

💡 Note: From [1,1] in 2x2 grid: Index 0 LURD: L→[1,0], U→[0,0], R→[0,1], D→[1,1] all valid = 4 steps. Index 1 URD: U→[0,1], R→would go to [0,2] out of bounds = 1 step.

Example 3 — Edge Position

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

› Output: [0,0,0,0]

💡 Note: In 1x1 grid at [0,0], any movement L,R,U,D goes out of bounds immediately, so 0 steps for all starting positions.

Constraints

1 ≤ n ≤ 1000
0 ≤ startPos[0], startPos[1] < n
1 ≤ s.length ≤ 1000
s consists of 'L', 'R', 'U', and 'D'

Visualization

Tap to expand

Understanding the Visualization

Input

Grid size n=3, start=[0,1], instructions="RRDDLU"

Process

For each suffix, simulate movement until boundary hit

Output

Array showing instruction count for each starting index

Key Takeaway

🎯 Key Insight: Each suffix needs independent simulation to count valid robot moves before boundary collision

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to simulate robot movement for each possible starting instruction position. For each suffix of instructions, we track the robot's position and count valid moves until it hits a boundary. The optimal approach uses direction mapping for cleaner code. Time: O(m²), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Simulation for Each Suffix	O(m²)	O(1)	Simulate robot movement for each possible starting instruction index
Optimized Simulation with Early Termination	O(m²)	O(1)	Same simulation approach but with cleaner bounds checking and direction mapping

Simulation for Each Suffix — Algorithm Steps

Step 1: For each starting index i, reset robot to initial position
Step 2: Execute instructions from index i onwards until boundary hit or end reached
Step 3: Count and store the number of successfully executed instructions

Visualization

Tap to expand

Step-by-Step Walkthrough

Start Position

Robot begins at startPos for each suffix

Execute Instructions

Follow instructions until boundary hit

Count Steps

Record number of successful moves

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void solution(int n, int* startPos, char* s, int* answer) {
    int m = strlen(s);
    
    for (int i = 0; i < m; i++) {
        int row = startPos[0], col = startPos[1];
        int count = 0;
        
        for (int j = i; j < m; j++) {
            // Calculate next position based on instruction
            int nextRow = row, nextCol = col;
            if (s[j] == 'L') {
                nextCol = col - 1;
            } else if (s[j] == 'R') {
                nextCol = col + 1;
            } else if (s[j] == 'U') {
                nextRow = row - 1;
            } else { // 'D'
                nextRow = row + 1;
            }
            
            // Check if next position is within bounds
            if (nextRow >= 0 && nextRow < n && nextCol >= 0 && nextCol < n) {
                row = nextRow;
                col = nextCol;
                count++;
            } else {
                break;
            }
        }
        
        answer[i] = count;
    }
}

int main() {
    int n;
    scanf("%d", &n);
    
    int startPos[2];
    scanf(" [%d,%d]", &startPos[0], &startPos[1]);
    
    char s[1001];
    scanf("%s", s);
    
    int m = strlen(s);
    int* answer = (int*)malloc(m * sizeof(int));
    solution(n, startPos, s, answer);
    
    printf("[");
    for (int i = 0; i < m; i++) {
        printf("%d", answer[i]);
        if (i < m - 1) printf(",");
    }
    printf("]\n");
    
    free(answer);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m²)

For each of m starting positions, we potentially execute up to m instructions

✓ Linear Growth

Space Complexity

O(1)

Only using variables to track position and count, no extra data structures

✓ Linear Space

25.0K Views

Medium Frequency

~15 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Simulation for Each Suffix — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler