Execution of All Suffix Instructions Staying in a Grid

Med

#1930Time: 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).

Data structures

String

Prompt

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 = [start_row, start_col] indicates that a robot is initially at cell (start_row, start_col).

You are also given a 0-indexed string s of length m where s[i] is the i^th instruction for the robot: 'L' (move left), 'R' (move right), 'U' (move up), and 'D' (move down).

The robot can begin executing from any i^th 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 i^th 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 <= start_row, start_col < n
s consists of 'L', 'R', 'U', and 'D'.

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1class Solution {2    public int[] executeInstructions(int n, int[] startPos, String s) {3        int m = s.length();4        int[] answer = new int[m];5 6        for (int i = 0; i < m; i++) {7            int count = 0;8            int row = startPos[0];9            int col = startPos[1];10 11            for (int j = i; j < m; j++) {12                char instruction = s.charAt(j);13                if (instruction == 'R') {14                    col++;15                } else if (instruction == 'L') {16                    col--;17                } else if (instruction == 'U') {18                    row--;19                } else if (instruction == 'D') {20                    row++;21                }22 23                if (row >= 0 && row < n && col >= 0 && col < n) {24                    count++;25                } else {26                    break;27                }28            }29            answer[i] = count;30        }31        return answer;32    }33}

Complexity

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

Trade-offs

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.

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.

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

Walkthrough

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

1(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.

1// This is a conceptual code snippet. A full implementation would require2// a helper class for a Sparse Table or Segment Tree for Range Min/Max Queries.3 4class Solution {5    // Assume RMQ query methods queryMin/queryMax exist and are pre-computed6    // on the prefix sum arrays. For example:7    // int queryMin(int[] arr, int l, int r);8    // int queryMax(int[] arr, int l, int r);9 10    public int[] executeInstructions(int n, int[] startPos, String s) {11        int m = s.length();12        int[] answer = new int[m];13        14        int[] prefix_row = new int[m + 1];15        int[] prefix_col = new int[m + 1];16        for (int i = 0; i < m; i++) {17            prefix_row[i+1] = prefix_row[i];18            prefix_col[i+1] = prefix_col[i];19            char move = s.charAt(i);20            if (move == 'U') prefix_row[i+1]--;21            else if (move == 'D') prefix_row[i+1]++;22            else if (move == 'L') prefix_col[i+1]--;23            else if (move == 'R') prefix_col[i+1]++;24        }25 26        // Pre-build RMQ structures for prefix_row and prefix_col here...27        // E.g., SparseTable st_row_min = new SparseTable(prefix_row, "min");28 29        for (int i = 0; i < m; i++) {30            int low = 0, high = m - i, ans = 0;31            while (low <= high) {32                int k = low + (high - low) / 2;33                if (k == 0) {34                    low = k + 1;35                    continue;36                }37                38                // Find min/max of prefix sums in the range of steps39                int min_r = queryMin(prefix_row, i + 1, i + k);40                int max_r = queryMax(prefix_row, i + 1, i + k);41                int min_c = queryMin(prefix_col, i + 1, i + k);42                int max_c = queryMax(prefix_col, i + 1, i + k);43 44                // Check if path stays within grid by checking extreme displacements45                if (startPos[0] + (min_r - prefix_row[i]) >= 0 &&46                    startPos[0] + (max_r - prefix_row[i]) < n &&47                    startPos[1] + (min_c - prefix_col[i]) >= 0 &&48                    startPos[1] + (max_c - prefix_col[i]) < n) {49                    ans = k;50                    low = k + 1; // Try for more moves51                } else {52                    high = k - 1; // Too many moves, reduce the number53                }54            }55            answer[i] = ans;56        }57        return answer;58    }59}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class 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 ; } }

1class 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 ; } };

1class 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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem