# Execution of All Suffix Instructions Staying in a Grid
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/execution-of-all-suffix-instructions-staying-in-a-grid)
Canonical: https://scaleengineer.com/dsa/problems/execution-of-all-suffix-instructions-staying-in-a-grid
**Data structures:** String
---
## 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:**

![](https://assets.glich.co/dsa/execution-of-all-suffix-instructions-staying-in-a-grid/image0.png) 

**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: "**R**RDDLU". 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:     "**L**U". 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:**

![](https://assets.glich.co/dsa/execution-of-all-suffix-instructions-staying-in-a-grid/image1.png) 

**Input:** n = 2, startPos = [1,1], s = "LURD"
**Output:** [4,1,0,0]
**Explanation:**
- 0th: "**LURD**".
- 1st:  "**U**RD".
- 2nd:   "RD".
- 3rd:    "D".

**Example 3:**

![](https://assets.glich.co/dsa/execution-of-all-suffix-instructions-staying-in-a-grid/image2.png) 

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

# Approaches
## Brute-Force Simulation
This approach directly simulates the process described in the problem. For each possible starting instruction index `i` from `0` to `m-1`, we trace the robot's path and count the number of valid moves until it either goes off the grid or runs out of instructions.
**Time:** O(m^2), where `m` is the length of the instruction string `s`. The outer loop runs `m` times, and the inner loop can also run up to `m` times. In total, the number of simulation steps is proportional to `m + (m-1) + ... + 1`, which sums to `O(m^2)`. · **Space:** O(m) to store the output array. The auxiliary space used is O(1).
**Pros:** Simple to understand and implement.; Low constant factor in complexity.; Sufficiently fast for the given constraints (`n, m <= 500`).
**Cons:** Inefficient for larger values of `m` due to its quadratic time complexity.; Recomputes paths repeatedly. For example, the path for `i=1` is a suffix of the path for `i=0`, but it's completely re-calculated.
### Explanation
We iterate through each index `i` of the instruction string `s`, considering it as the starting point of execution. For each `i`, we reset the robot's position to `startPos` and initialize a counter for the number of executed instructions to zero.

Then, we start a nested loop to execute instructions from index `i` to the end of the string. In each step of this inner loop, we update the robot's current row and column based on the instruction ('U', 'D', 'L', 'R'). After each move, we check if the robot's new position is still within the `n x n` grid boundaries (i.e., `0 <= row < n` and `0 <= col < n`).

If the robot remains within the grid, we increment our instruction counter. If it moves off the grid, we stop executing instructions for the current starting index `i` and break the inner loop. The final value of the counter for each `i` is stored in the result array `answer[i]`. This process is repeated for all possible starting indices.

```java
class Solution {
    public 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 count = 0;
            int row = startPos[0];
            int col = startPos[1];

            for (int j = i; j < m; j++) {
                char instruction = s.charAt(j);
                if (instruction == 'R') {
                    col++;
                } else if (instruction == 'L') {
                    col--;
                } else if (instruction == 'U') {
                    row--;
                } else if (instruction == 'D') {
                    row++;
                }

                if (row >= 0 && row < n && col >= 0 && col < n) {
                    count++;
                } else {
                    break;
                }
            }
            answer[i] = count;
        }
        return answer;
    }
}
```
### Algorithm
- Initialize an array `answer` of size `m`, where `m` is the length of `s`.
- Loop for `i` from `0` to `m-1`:
    - Initialize `count = 0`.
    - Set current position `(row, col)` to `(startPos[0], startPos[1])`.
    - Loop for `j` from `i` to `m-1`:
        - Read instruction `s[j]`.
        - Update `row` and `col` based on the instruction.
        - Check if `(row, col)` is within the grid (`0 <= row < n` and `0 <= col < n`).
        - If it is, increment `count`.
        - If not, break the inner loop.
    - Store `count` in `answer[i]`.
- Return `answer`.

## Prefix Sums with Binary Search and RMQ
This approach avoids re-simulation by pre-calculating movement effects and then using binary search to find the number of valid moves. The core idea is to determine for each starting point how many steps can be taken before hitting any of the four grid boundaries.
**Time:** O(m log m). Building the Sparse Table takes `O(m log m)`. Then, for each of the `m` starting positions, we perform a binary search which takes `O(log m)` time. Each check inside the binary search is an `O(1)` RMQ query. Total time is `O(m log m + m * log m) = O(m log m)`. · **Space:** O(m log m). The prefix sum arrays take `O(m)` space. The Sparse Tables for min and max on two arrays take `O(m log m)` space.
**Pros:** Much more efficient than the brute-force approach for large `m`.; Demonstrates use of advanced data structures and algorithmic techniques like prefix sums, binary search, and RMQ.
**Cons:** Significantly more complex to implement correctly compared to the brute-force approach.; Higher space complexity due to the RMQ data structure.; This level of optimization is not strictly necessary for the given constraints but would be crucial for larger inputs.
### Explanation
First, we can observe that the robot's position after a sequence of moves depends only on the net change in row and column. We can precompute these net changes using prefix sums. Let `prefix_row[k]` and `prefix_col[k]` be the net change in row and column after the first `k` instructions `s[0...k-1]`. These can be computed in `O(m)` time.

The position after `l` moves starting from instruction `s[i]` is `(startPos[0] + (prefix_row[i+l] - prefix_row[i]), startPos[1] + (prefix_col[i+l] - prefix_col[i]))`. For a path to be valid, all intermediate positions must be within the grid. This is equivalent to checking if the minimum and maximum row/column coordinates reached during this path are within the grid boundaries.

For each starting index `i`, we can binary search for the maximum number of steps `k` that the robot can execute. The `check(k)` function for the binary search would verify if a path of length `k` is valid. To do this check efficiently, we need to find the minimum and maximum values in sub-arrays of our prefix sum arrays (e.g., `min(prefix_row[i+1...i+k])`). This is a Range Minimum/Maximum Query (RMQ) problem. We can build a data structure like a Sparse Table in `O(m log m)` to answer these queries in `O(1)`.

The overall algorithm is to first build the prefix sum arrays and the RMQ structure. Then, for each `i`, binary search for the answer `k`.

```java
// This is a conceptual code snippet. A full implementation would require
// a helper class for a Sparse Table or Segment Tree for Range Min/Max Queries.

class Solution {
    // Assume RMQ query methods queryMin/queryMax exist and are pre-computed
    // on the prefix sum arrays. For example:
    // int queryMin(int[] arr, int l, int r);
    // int queryMax(int[] arr, int l, int r);

    public int[] executeInstructions(int n, int[] startPos, String s) {
        int m = s.length();
        int[] answer = new int[m];
        
        int[] prefix_row = new int[m + 1];
        int[] prefix_col = new int[m + 1];
        for (int i = 0; i < m; i++) {
            prefix_row[i+1] = prefix_row[i];
            prefix_col[i+1] = prefix_col[i];
            char move = s.charAt(i);
            if (move == 'U') prefix_row[i+1]--;
            else if (move == 'D') prefix_row[i+1]++;
            else if (move == 'L') prefix_col[i+1]--;
            else if (move == 'R') prefix_col[i+1]++;
        }

        // Pre-build RMQ structures for prefix_row and prefix_col here...
        // E.g., SparseTable st_row_min = new SparseTable(prefix_row, "min");

        for (int i = 0; i < m; i++) {
            int low = 0, high = m - i, ans = 0;
            while (low <= high) {
                int k = low + (high - low) / 2;
                if (k == 0) {
                    low = k + 1;
                    continue;
                }
                
                // Find min/max of prefix sums in the range of steps
                int min_r = queryMin(prefix_row, i + 1, i + k);
                int max_r = queryMax(prefix_row, i + 1, i + k);
                int min_c = queryMin(prefix_col, i + 1, i + k);
                int max_c = queryMax(prefix_col, i + 1, i + k);

                // Check if path stays within grid by checking extreme displacements
                if (startPos[0] + (min_r - prefix_row[i]) >= 0 &&
                    startPos[0] + (max_r - prefix_row[i]) < n &&
                    startPos[1] + (min_c - prefix_col[i]) >= 0 &&
                    startPos[1] + (max_c - prefix_col[i]) < n) {
                    ans = k;
                    low = k + 1; // Try for more moves
                } else {
                    high = k - 1; // Too many moves, reduce the number
                }
            }
            answer[i] = ans;
        }
        return answer;
    }
}
```
### Algorithm
- Precompute prefix sum arrays `prefix_row` and `prefix_col` of size `m+1`. `prefix_row[k]` stores the net row change after instructions `s[0...k-1]`.
- For each starting index `i` from `0` to `m-1`:
    - We want to find the maximum `k` (`0 <= k <= m-i`) such that for all `l` from `1` to `k`, the robot stays on the grid.
    - The position after `l` moves is `(startPos[0] + prefix_row[i+l] - prefix_row[i], startPos[1] + prefix_col[i+l] - prefix_col[i])`.
    - The path is valid if for all `l` in `[1, k]`, the position is within bounds. This is equivalent to checking if the minimum and maximum coordinates over the path are within grid boundaries.
    - We can binary search for `k` in `[0, m-i]`.
    - To check a given `k` efficiently, we need Range Min/Max Query (RMQ). We can pre-build a Sparse Table for `prefix_row` and `prefix_col` in `O(m log m)` time, which allows `O(1)` time queries.
    - For a given `k`, the check involves four RMQ queries on the range `[i+1, i+k]` to find the min/max of prefix sums and comparing them against bounds derived from `startPos`, `n`, `prefix_row[i]`, and `prefix_col[i]`.
    - The binary search for each `i` takes `O(log m)` time.
- The total time complexity is `O(m log m)`.

# Solutions
### Java

```java
class Solution { public int [] executeInstructions ( int n , int [] startPos , String s ) { int m = s . length (); int [] ans = new int [ m ]; Map < Character , int []> mp = new HashMap <>( 4 ); mp . put ( 'L' , new int [] { 0 , - 1 }); mp . put ( 'R' , new int [] { 0 , 1 }); mp . put ( 'U' , new int [] {- 1 , 0 }); mp . put ( 'D' , new int [] { 1 , 0 }); for ( int i = 0 ; i < m ; ++ i ) { int x = startPos [ 0 ], y = startPos [ 1 ]; int t = 0 ; for ( int j = i ; j < m ; ++ j ) { char c = s . charAt ( j ); int a = mp . get ( c )[ 0 ], b = mp . get ( c )[ 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 ; } }
```

### CPP

```cpp
class Solution { public: vector < int > executeInstructions ( int n , vector < int >& startPos , string s ) { int m = s . size (); vector < int > ans ( m ); unordered_map < char , vector < int >> mp ; mp [ 'L' ] = { 0 , - 1 }; mp [ 'R' ] = { 0 , 1 }; mp [ 'U' ] = { - 1 , 0 }; mp [ 'D' ] = { 1 , 0 }; for ( int i = 0 ; i < m ; ++ i ) { int x = startPos [ 0 ], y = startPos [ 1 ]; int t = 0 ; for ( int j = i ; j < m ; ++ j ) { int a = mp [ s [ j ]][ 0 ], b = 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 ; } };
```

### Python

```python
class Solution : def executeInstructions ( self , n : int , startPos : List [ int ], s : str ) -> List [ int ]: ans = [] m = len ( s ) mp = { "L" : [ 0 , - 1 ], "R" : [ 0 , 1 ], "U" : [ - 1 , 0 ], "D" : [ 1 , 0 ]} for i in range ( m ): x , y = startPos t = 0 for j in range ( i , m ): a , b = mp [ s [ j ]] if 0 <= x + a < n and 0 <= y + b < n : x , y , t = x + a , y + b , t + 1 else : break ans . append ( t ) return ans
```