Walking Robot Simulation - Practice Coding Problems

Walking Robot Simulation - Problem

A robot on an infinite XY-plane starts at point (0, 0) facing north. The robot receives an array of integers commands, which represents a sequence of moves that it needs to execute.

There are only three possible types of instructions the robot can receive:

-2: Turn left 90 degrees
-1: Turn right 90 degrees
1 <= k <= 9: Move forward k units, one unit at a time

Some of the grid squares are obstacles. The i-th obstacle is at grid point obstacles[i] = (xi, yi). If the robot runs into an obstacle, it will stay in its current location (on the block adjacent to the obstacle) and move onto the next command.

Return the maximum squared Euclidean distance that the robot reaches at any point in its path (i.e. if the distance is 5, return 25).

Note:

There can be an obstacle at (0, 0). If this happens, the robot will ignore the obstacle until it has moved off the origin. However, it will be unable to return to (0, 0) due to the obstacle.
North means +Y direction, East means +X direction, South means -Y direction, West means -X direction.

Input & Output

Example 1 — Basic Movement with Obstacles

$ Input: commands = [4,-1,4,-2,-1,-2,3], obstacles = [[2,1],[1,1]]

› Output: 25

💡 Note: Robot moves (0,0)→(0,1)→(0,2)→(0,3)→(0,4), turns right to face East, tries to move but hits obstacle at (1,1), continues with other commands. Maximum distance reached is √25 = 5, so return 25.

Example 2 — No Obstacles

$ Input: commands = [4,-1,3], obstacles = []

› Output: 25

💡 Note: Robot moves North 4 units to (0,4), turns right to face East, moves 3 units to (3,4). Max distance² = 3² + 4² = 9 + 16 = 25.

Example 3 — Blocked at Origin

$ Input: commands = [1,2,-2,5], obstacles = [[0,1]]

› Output: 0

💡 Note: Robot tries to move North but hits obstacle at (0,1) immediately. Stays at (0,0) and processes remaining commands but never moves. Max distance² = 0.

Constraints

1 ≤ commands.length ≤ 10⁴
commands[i] is either -2, -1, or in the range [1, 9]
0 ≤ obstacles.length ≤ 10⁴
-3 × 10⁴ ≤ xi, yi ≤ 3 × 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Robot commands and obstacle positions

Process

Simulate movement with obstacle checking

Output

Maximum squared Euclidean distance

Key Takeaway

🎯 Key Insight: Use hash set for O(1) obstacle detection during step-by-step robot simulation

Asked in

a Amazon 45 G Google 38 f Facebook 22 M Microsoft 18

The key insight is to use a hash set for O(1) obstacle lookup while simulating the robot's movement step by step. Convert obstacles to a hash set, then simulate each command by updating direction or position. Best approach is Hash Set Optimization with Time: O(C×S+O), Space: O(O).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Simulation	O(C × S × O)	O(1)	Simulate each command, checking obstacles by scanning the entire obstacles array
Hash Set Optimization	O(C × S + O)	O(O)	Use a hash set for O(1) obstacle lookup during simulation

Brute Force Simulation — Algorithm Steps

Initialize robot at (0,0) facing north
For each command, process turn or movement
For movement, check each step against all obstacles
Update maximum squared distance

Visualization

Tap to expand

Step-by-Step Walkthrough

Robot Position

Track robot at (x,y) with direction

Linear Obstacle Check

For each step, scan all obstacles

Update Maximum

Track max squared distance

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* commands, int commandsSize, int** obstacles, int obstaclesSize) {
    int x = 0, y = 0;
    int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // North, East, South, West
    int directionIdx = 0;
    int maxDistSq = 0;
    
    for (int i = 0; i < commandsSize; i++) {
        int command = commands[i];
        if (command == -2) { // Turn left
            directionIdx = (directionIdx - 1 + 4) % 4;
        } else if (command == -1) { // Turn right
            directionIdx = (directionIdx + 1) % 4;
        } else { // Move forward
            int dx = directions[directionIdx][0];
            int dy = directions[directionIdx][1];
            for (int j = 0; j < command; j++) {
                int newX = x + dx;
                int newY = y + dy;
                // Check if new position is an obstacle
                int isObstacle = 0;
                for (int k = 0; k < obstaclesSize; k++) {
                    if (obstacles[k][0] == newX && obstacles[k][1] == newY) {
                        isObstacle = 1;
                        break;
                    }
                }
                if (!isObstacle) {
                    x = newX;
                    y = newY;
                    int distSq = x*x + y*y;
                    if (distSq > maxDistSq) {
                        maxDistSq = distSq;
                    }
                } else {
                    break; // Stop moving if obstacle hit
                }
            }
        }
    }
    
    return maxDistSq;
}

int main() {
    // Simplified parsing for demonstration
    int commands[] = {4, -1, 4, -2, -1, -2, 3};
    int commandsSize = 7;
    int obs1[] = {2, 1};
    int obs2[] = {1, 1};
    int* obstacles[] = {obs1, obs2};
    int obstaclesSize = 2;
    
    printf("%d\n", solution(commands, commandsSize, obstacles, obstaclesSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(C × S × O)

C commands, up to S=9 steps per move, O obstacles to check each step

✓ Linear Growth

Space Complexity

O(1)

Only variables for position, direction, and maximum distance

✓ Linear Space

34.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler