We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Execution of All Suffix Instructions Staying in a Grid

Difficulty: Medium

Problem Description

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.

Key Insights

  • The robot must stay within the grid boundaries while executing instructions.
  • Starting from each instruction, we need to simulate the movement and count how many instructions can be executed before going out of bounds.
  • The problem can be solved efficiently by iterating from the end of the instruction string to the beginning to avoid redundant calculations.

Space and Time Complexity

Time Complexity: O(m) - Each instruction is processed once. Space Complexity: O(m) - An array to store the results of the execution counts.

Solution

The solution involves simulating the robot's movement within the grid. We start from the last instruction and move backwards, keeping track of the robot's position. For each instruction, we check if the next move would go out of bounds. If it does, we stop counting; otherwise, we continue to count how many instructions can be executed from that starting point.

We can use a simple array to store the number of executable instructions for each starting point.

Code Solutions

def executeInstructions(n, startPos, s):
    m = len(s)
    answer = [0] * m
    row, col = startPos
    
    for i in range(m - 1, -1, -1):
        # Initialize position for the current instruction
        current_row, current_col = row, col
        count = 0
        
        # Iterate through instructions starting from i
        for j in range(i, m):
            if s[j] == 'L':
                current_col -= 1
            elif s[j] == 'R':
                current_col += 1
            elif s[j] == 'U':
                current_row -= 1
            elif s[j] == 'D':
                current_row += 1
            
            # Check if the current position is out of bounds
            if current_row < 0 or current_row >= n or current_col < 0 or current_col >= n:
                break
            
            count += 1
        
        answer[i] = count
    
    return answer
← Back to All Questions