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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Execution of All Suffix Instructions Staying in a Grid

Number: 2239

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given an n x n grid with coordinates ranging from (0,0) at the top-left to (n-1, n-1) at the bottom-right, a robot is placed at startPos. You are provided a string s consisting of instructions ('L', 'R', 'U', 'D'). For each starting index in s, the robot executes instructions one by one until it either leaves the grid or runs out of instructions. The goal is to compute an array where each element corresponds to the number of valid moves executed when starting from that instruction index.

Key Insights

  • Simulate the robot’s movement for each suffix of the instruction string.
  • Check boundaries after every move to ensure the robot stays inside the grid.
  • Use simple iteration for simulation since the maximum length (m) is limited (m ≤ 500).
  • Although the brute-force simulation is O(m^2), it is efficient enough given the constraints.

Space and Time Complexity

Time Complexity: O(m^2), where m is the length of the instruction string, because for each starting index we might simulate up to m steps. Space Complexity: O(m) to store the answer array.

Solution

We iterate over each index in the instruction string and simulate the robot’s movement starting at the given position. For each move, we update the robot’s coordinates according to the instruction and check if the new position is out of bounds. If it is, the simulation for that suffix stops and the count of valid moves is stored. This simulation uses a simple iteration and comparison approach.

Code Solutions

def executeInstructions(n, startPos, s):
    m = len(s)
    answer = []
    # Simulate starting from every index in s
    for i in range(m):
        steps = 0
        row, col = startPos  # Reset start position for each simulation
        for j in range(i, m):
            # Update position based on current instruction
            if s[j] == 'L':
                col -= 1
            elif s[j] == 'R':
                col += 1
            elif s[j] == 'U':
                row -= 1
            elif s[j] == 'D':
                row += 1
            
            # Stop if the robot goes off the grid
            if row < 0 or row >= n or col < 0 or col >= n:
                break
            steps += 1  # Count valid move
        answer.append(steps)
    return answer

# Example usage:
print(executeInstructions(3, [0, 1], "RRDDLU"))
← Back to All Questions