Leetcode 874. Walking Robot Simulation

Problem

You are simulating a robot moving on an infinite 2D grid. The robot starts at the origin point (0, 0) facing north (positive Y direction).

The robot receives a sequence of commands:

• A positive integer k means move forward k units in the current direction
• -1 means turn right 90 degrees
• -2 means turn left 90 degrees

The grid also contains obstacles at specific coordinates. When executing a forward movement command, the robot moves one unit at a time. If the next step would place the robot on an obstacle, the robot stops moving for that command (but retains its direction) and proceeds to the next command.

Your task is to simulate the robot's movement and return the maximum squared Euclidean distance from the origin that the robot reaches at any point during its journey.

The squared Euclidean distance for a point (x, y) is calculated as x² + y².

Requirements

1. Process each command sequentially in the order given
2. For movement commands, advance one unit at a time (not all at once)
3. Stop immediately if the next unit step would collide with an obstacle
4. Track the maximum squared distance from origin throughout the entire path
5. Use an efficient data structure for obstacle lookup (O(1) average case)

Constraints

• 1 ≤ commands.length ≤ 10⁴
• commands[i] is either -2, -1, or an integer in the range [1, 9]
• 0 ≤ obstacles.length ≤ 10⁴
• -3 × 10⁴ ≤ obstacles[i][0], obstacles[i][1] ≤ 3 × 10⁴
• The robot will never start on an obstacle
• All obstacle coordinates are unique

Examples

Example 1:

` Input: commands = [4, -1, 3], obstacles = [] Output: 25 Explanation:

• Robot starts at (0, 0) facing north
• Move 4 units north to (0, 4)
• Turn right to face east
• Move 3 units east to (3, 4)
• Maximum squared distance: 3² + 4² = 25 `

Example 2:

` Input: commands = [4, -1, 4, -2, 4], obstacles = [[2, 4]] Output: 65 Explanation:

• Robot moves north to (0, 4)
• Turns right to face east
• Attempts to move 4 units east but stops at (1, 4) due to obstacle at (2, 4)
• Turns left to face north again
• Moves 4 units north to (1, 8)
• Maximum squared distance: 1² + 8² = 65 `

Example 3:

Input: commands = [-1, -1, -2, -2], obstacles = [] Output: 0 Explanation: Robot only turns and never moves from origin.

Hint 1: Direction Representation Represent the four cardinal directions using direction vectors. For example, north can be (0, 1), east can be (1, 0), south can be (0, -1), and west can be (-1, 0). Store these in an array and use an index to track the current facing direction. Turning right or left simply increments or decrements this index.

Hint 2: Obstacle Lookup Convert the obstacles list into a set of tuples or a set of encoded strings for O(1) lookup time. Before each step, check if the next position exists in this set. This is crucial for performance with many obstacles.

Hint 3: Step-by-Step Movement When processing a forward movement command of k units, don't jump directly to the final position. Instead, move one unit at a time in a loop, checking for obstacles before each individual step. Update the maximum distance after each successful step.

Full Solution `` Approach:

1. Direction Management: Use an array of direction vectors [(0,1), (1,0), (0,-1), (-1,0)] representing north, east, south, and west. Maintain an index to track the current facing direction, updating it with modulo arithmetic for turns.
2. Obstacle Lookup: Convert the obstacles list into a set of tuples for constant-time membership checking. This is critical when the robot needs to verify if the next position is blocked.
3. Incremental Movement: For each forward movement command, advance one unit at a time rather than jumping to the final position. Before each step, check if the next position contains an obstacle. If so, stop processing that command immediately.
4. Distance Tracking: After each successful movement, calculate the squared Euclidean distance and update the maximum if necessary.

Time Complexity: O(N + M) where N is the total number of unit steps taken (sum of all forward commands) and M is the number of obstacles (for set construction).

Space Complexity: O(M) for storing obstacles in the set.

def robotSim(commands, obstacles):
    # Starting position and direction
    x, y = 0, 0
    
    # Direction vectors: North, East, South, West
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    direction_idx = 0  # Start facing North
    
    # Convert obstacles to a set for O(1) lookup
    obstacle_set = set(map(tuple, obstacles))
    
    # Track maximum squared distance
    max_dist_sq = 0
    
    # Process each command
    for cmd in commands:
        if cmd == -1:  # Turn right
            direction_idx = (direction_idx + 1) % 4
        elif cmd == -2:  # Turn left
            direction_idx = (direction_idx - 1) % 4
        else:  # Move forward cmd units
            dx, dy = directions[direction_idx]
            # Move one unit at a time
            for _ in range(cmd):
                next_x, next_y = x + dx, y + dy
                # Check if next position is an obstacle
                if (next_x, next_y) not in obstacle_set:
                    x, y = next_x, next_y
                    # Update maximum squared distance
                    max_dist_sq = max(max_dist_sq, x * x + y * y)
                else:
                    # Hit an obstacle, stop moving for this command
                    break
    
    return max_dist_sq