Leetcode 2120: Execution of All Suffix Instructions Staying in a Grid

Input: You are given the size of the grid n, the starting position startPos, and a string s of instructions.

Example: n = 3, startPos = [0, 1], s = 'RRDDLU'

Constraints:

• 1 <= n, m <= 500

• startPos.length == 2

• 0 <= startrow, startcol < n

• s consists of 'L', 'R', 'U', and 'D'.

Output: Return an array of integers where each element at index i represents the number of instructions that can be executed if the robot begins at the ith instruction in the sequence.

Example: For n = 3, startPos = [0, 1], s = 'RRDDLU', the output is [1, 5, 4, 3, 1, 0].

Constraints:

Goal: To determine how many instructions the robot can execute starting from each index in the instruction string while staying within the bounds of the grid.

Steps:

• For each instruction in the string s, simulate the robot's movement starting from that position, tracking the number of valid moves.

• Stop the simulation if the robot moves off the grid or there are no more instructions to process.

• Store the number of valid instructions the robot can execute starting from each index and return the result.

Goal: The solution must work efficiently for the maximum input size.

Steps:

• The grid size n and the instruction string length m are both capped at 500.

Assumptions:

• The robot will always start within the bounds of the grid.

• Input: Example 1: n = 3, startPos = [0, 1], s = 'RRDDLU'

• Explanation: Starting from the initial position (0, 1), the robot can execute the following instructions starting from each index: 1 move from index 0 ('R'), 5 moves from index 1 ('RDDLU'), and so on.

• Input: Example 2: n = 2, startPos = [1, 1], s = 'LURD'

• Explanation: From position (1, 1), the robot can execute the following instructions starting from each index: 4 moves from index 0 ('LURD'), 1 move from index 1 ('URD'), and so on.

• Input: Example 3: n = 1, startPos = [0, 0], s = 'LRUD'

• Explanation: Since the grid is of size 1x1, no moves can be executed, and the result is [0, 0, 0, 0].

Approach: The approach is to simulate the robot's movement for each starting position and check how many valid moves it can make while staying within the grid.

Observations:

• We need to check each instruction starting from every index in the string s.

• We need to track the robot's position and stop when it moves off the grid.

• A simulation approach will work well here, ensuring that each instruction is processed for each possible starting point.

Steps:

• For each instruction in s, start simulating from the current index.

• Move the robot according to the instructions and check if it stays within the grid bounds.

• Keep track of the number of valid instructions executed and return the result for each starting index.

Empty Inputs:

• If n is 1, no movement is possible, so the result for all indices in s will be 0.

Large Inputs:

• Ensure that the solution works efficiently for n and m up to 500.

Special Values:

• If all instructions would cause the robot to move off the grid, the result will be 0 for every index.

Constraints:

• The solution should handle the largest grid size and instruction string length efficiently.

vector<int> executeInstructions(int n, vector<int>& st, string s) {
    int m = s.size(), h = m + n, v = m + n;
    vector<int> hor((h + m) * 2, m), ver((h +m) * 2, m), res(m);
    for(int i = m - 1; i >= 0; i--) {
        hor[h] = ver[v] = i;
        h += s[i] == 'L' ? 1 : s[i] == 'R'? -1 : 0;
        v += s[i] == 'U' ? 1 : s[i] == 'D'? -1 : 0;
        res[i] = min({  m, hor[h - st[1] - 1], hor[h - st[1] + n],
                           ver[v - st[0] - 1], ver[v - st[0] + n]  }) - i;
    }
    return res;
}

1 : Function Definition

vector<int> executeInstructions(int n, vector<int>& st, string s) {

Function definition for 'executeInstructions' which takes an integer n, a vector of integers st, and a string s as input. It returns a vector of integers as the result.

2 : Variable Initialization

    int m = s.size(), h = m + n, v = m + n;

This line initializes variables m (size of the string), h (horizontal position), and v (vertical position), both starting from m + n.

3 : Array Initialization

    vector<int> hor((h + m) * 2, m), ver((h +m) * 2, m), res(m);

Three vectors are initialized: hor (for horizontal positions), ver (for vertical positions), and res (for storing the result).

4 : For Loop

    for(int i = m - 1; i >= 0; i--) {

A for loop that iterates through the string s in reverse order, starting from the last character.

5 : Position Update

        hor[h] = ver[v] = i;

Updates the hor and ver arrays at the current positions of h and v to the current index i.

6 : Horizontal Movement

        h += s[i] == 'L' ? 1 : s[i] == 'R'? -1 : 0;

Adjusts the horizontal position (h) based on whether the current character in the string is 'L' (left), 'R' (right), or neither.

7 : Vertical Movement

        v += s[i] == 'U' ? 1 : s[i] == 'D'? -1 : 0;

Adjusts the vertical position (v) based on whether the current character in the string is 'U' (up), 'D' (down), or neither.

8 : Result Calculation

        res[i] = min({  m, hor[h - st[1] - 1], hor[h - st[1] + n],

Calculates the result for the current position by finding the minimum of various possible values based on horizontal movements.

9 : Result Calculation (cont.)

                           ver[v - st[0] - 1], ver[v - st[0] + n]  }) - i;

Continues the result calculation for vertical movements and subtracts the current index i.

10 : Return Statement

    return res;

Returns the result vector containing the calculated values.

Best Case: O(n * m)

Average Case: O(n * m)

Worst Case: O(n * m)

Description: The time complexity is O(n * m), where n is the grid size and m is the length of the instruction string.

Best Case: O(m)

Worst Case: O(m)

Description: The space complexity is O(m), as we store the result array of length m.

Leetcode 2120: Execution of All Suffix Instructions Staying in a Grid

Explore →