Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Walking Robot Simulation solution and explanation

MediumArrayHash TableSimulation8 min read64.5% acceptanceUpdated 9 Apr 2026
Asked atJane StreetShopifyPhonePeAmazonAppleGoogle
+1 moreMicrosoft
Practise Walking Robot Simulation
30:56
Walking Robot Simulation | Detailed Simulation | Leetcode 874 | codestorywithMIKcodestorywithMIK · 30:56 · 16K viewsWatch on YouTube
9 more videos on this problem
  1. Walking Robot Simulation | Detailed Simulation | Leetcode 874 | codestorywithMIKcodestorywithMIK · 30:56 · 16K views
  2. Walking Robot Simulation - Leetcode 874 - PythonNeetCodeIO · 14:02 · 13K views
  3. 874. Walking Robot Simulation | arrays | hashing | Leetcode Daily ChallengeShashCode · 17:16 · 4K views
  4. 874. Walking Robot Simulation | Leetcode Daily - PythonLeetcode Daily · 6:51 · 510 views
  5. Walking Robot Simulation | Leetcode 874 | Java | HindiKernel Queen 👑 · 11:35 · 491 views
  6. LeetCode 874 - Walking Robot Simulation - JavaAlpha-Code · 16:57 · 452 views
  7. 874. Walking Robot Simulation | Arrays | C++ | LeetcodeRapid Syntax · 16:17 · 426 views
  8. leetcode 874 | Walking Robot Simulation | Leetcode POTD | DSACode With Vick · 19:14 · 392 views
  9. Walking Robot Simulation - Leetcode 874 - JavaCode With K5KC · 10:13 · 249 views
  10. Walking Robot Simulation | LeetCode 874 - Pythonimpoldev · 10:05 · 199 views

The 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 ith 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.

Example 1:

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

Output: 25

Explanation:

The robot starts at (0, 0):

  1. Move north 4 units to (0, 4).
  2. Turn right.
  3. Move east 3 units to (3, 4).

The furthest point the robot ever gets from the origin is (3, 4), which squared is 32 + 42 = 25 units away.

Example 2:

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

Output: 65

Explanation:

The robot starts at (0, 0):

  1. Move north 4 units to (0, 4).
  2. Turn right.
  3. Move east 1 unit and get blocked by the obstacle at (2, 4), robot is at (1, 4).
  4. Turn left.
  5. Move north 4 units to (1, 8).

The furthest point the robot ever gets from the origin is (1, 8), which squared is 12 + 82 = 65 units away.

Example 3:

Input: commands = [6,-1,-1,6], obstacles = [[0,0]]

Output: 36

Explanation:

The robot starts at (0, 0):

  1. Move north 6 units to (0, 6).
  2. Turn right.
  3. Turn right.
  4. Move south 5 units and get blocked by the obstacle at (0,0), robot is at (0, 1).

The furthest point the robot ever gets from the origin is (0, 6), which squared is 62 = 36 units away.

Constraints:

  • 1 <= commands.length <= 104
  • commands[i] is either -2, -1, or an integer in the range [1, 9].
  • 0 <= obstacles.length <= 104
  • -3 * 104 <= xi, yi <= 3 * 104
  • The answer is guaranteed to be less than 231.

Approach overview

Problem Overview: You control a robot on an infinite 2D grid starting at (0,0) facing north. The robot receives commands to move forward or rotate left/right. Some grid cells contain obstacles that block movement. The task is to simulate the robot’s path and return the maximum Euclidean distance squared from the origin reached during the simulation.

Approach 1: Naive Simulation with Obstacle Scan (O(n * k) time, O(1) space)

The straightforward solution simulates each command step-by-step. For every forward movement, the robot advances one unit at a time while checking if the next coordinate matches any obstacle. If obstacles are stored in a list, every step requires scanning the entire list to determine whether movement is blocked. With k obstacles and up to n movement steps, this results in O(n * k) time complexity. The logic is simple and demonstrates how robot movement works, but obstacle lookup becomes the bottleneck as the number of obstacles grows.

Approach 2: Simulate Robot Movement Using Direction Array + Hash Set (O(n) time, O(k) space)

The optimal solution still performs step-by-step simulation but removes the expensive obstacle scan. Store all obstacle coordinates in a hash set so membership checks run in O(1) average time. Maintain a direction array such as [(0,1),(1,0),(0,-1),(-1,0)] representing north, east, south, and west. Rotation commands simply update a direction index using modulo arithmetic, while forward commands iterate step-by-step and check the next coordinate in the set. If the coordinate exists in the set, movement stops for that command. Otherwise update the robot’s position and track the maximum distance squared from the origin.

This approach relies heavily on constant-time lookups from a Hash Table and simple coordinate updates using an Array of direction vectors. The problem becomes a clean Simulation task where each step performs only a few arithmetic operations and one hash lookup.

Recommended for interviews: Interviewers expect the hash set + direction array approach. The naive scan demonstrates understanding of the robot simulation, but the optimized version shows you recognize the need for constant-time obstacle checks. Using a direction array keeps the code concise and avoids repeated conditional logic for turns.

Approach 1: Simulate Robot Movement Using Direction Array

Simulate the movement of the robot by maintaining a variable for the current direction. Use an array to store the possible directions: north, east, south, and west. When a turn command is received, adjust the direction index. For movement commands, move the robot in the direction indexed by the current direction.

def robotSim(commands, obstacles):
    obstacle_set = set(map(tuple, obstacles))
    # Directions: north, east, south, west
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    x = y = 0
    direction = 0
    max_distance_sq = 0

    for command in commands:
        if command == -2:  # Turn left
            direction = (direction - 1) % 4
        elif command == -1:  # Turn right
            direction = (direction + 1) % 4
        else:
            for _ in range(command):
                if (x + dx[direction], y + dy[direction]) not in obstacle_set:
                    x += dx[direction]
                    y += dy[direction]
                else:
                    break
            max_distance_sq = max(max_distance_sq, x * x + y * y)

    return max_distance_sq
import java.util.HashSet;
import java.util.Set;

public class Robot {
    public int robotSim(int[] commands, int[][] obstacles) {
        Set<String> obstacleSet = new HashSet<>();
        for (int[] obs : obstacles) {
            obstacleSet.add(obs[0] + "," + obs[1]);
        }

        int[] dx = {0, 1, 0, -1};
        int[] dy = {1, 0, -1, 0};
        int x = 0, y = 0, direction = 0, maxDistSq = 0;

        for (int cmd : commands) {
            if (cmd == -2) { // Turn left
                direction = (direction + 3) % 4;
            } else if (cmd == -1) { // Turn right
                direction = (direction + 1) % 4;
            } else {
                for (int k = 0; k < cmd; k++) {
                    int nx = x + dx[direction];
                    int ny = y + dy[direction];
                    if (!obstacleSet.contains(nx + "," + ny)) {
                        x = nx;
                        y = ny;
                        maxDistSq = Math.max(maxDistSq, x * x + y * y);
                    } else {
                        break;
                    }
                }
            }
        }

        return maxDistSq;
    }
}
#include <vector>
#include <unordered_set>
using namespace std;

struct pair_hash {
    template <class T1, class T2>
    size_t operator () (const pair<T1, T2>& pair) const {
        return hash<T1>()(pair.first) ^ hash<T2>()(pair.second);
    }
};

int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
    unordered_set<pair<int,int>, pair_hash> obstacle_set;
    for (auto& obs : obstacles) {
        obstacle_set.insert({obs[0], obs[1]});
    }
    vector<int> dx = {0, 1, 0, -1};
    vector<int> dy = {1, 0, -1, 0};
    int x = 0, y = 0, direction = 0, max_dist_sq = 0;

    for (int cmd : commands) {
        if (cmd == -2) { // Turn left
            direction = (direction + 3) % 4;
        } else if (cmd == -1) { // Turn right
            direction = (direction + 1) % 4;
        } else {
            for (int k = 0; k < cmd; ++k) {
                int nx = x + dx[direction];
                int ny = y + dy[direction];
                if (obstacle_set.find({nx, ny}) == obstacle_set.end()) {
                    x = nx;
                    y = ny;
                    max_dist_sq = max(max_dist_sq, x * x + y * y);
                } else {
                    break;
                }
            }
        }
    }

    return max_dist_sq;
}
function robotSim(commands, obstacles) {
    const obstacleSet = new Set(obstacles.map(obs => obs.toString()));
    const dx = [0, 1, 0, -1];
    const dy = [1, 0, -1, 0];
    let x = 0, y = 0, direction = 0, maxDistSq = 0;

    for (const cmd of commands) {
        if (cmd === -2) { // Turn left
            direction = (direction + 3) % 4;
        } else if (cmd === -1) { // Turn right
            direction = (direction + 1) % 4;
        } else {
            for (let k = 0; k < cmd; k++) {
                const nx = x + dx[direction];
                const ny = y + dy[direction];
                if (!obstacleSet.has([nx, ny].toString())) {
                    x = nx;
                    y = ny;
                    maxDistSq = Math.max(maxDistSq, x * x + y * y);
                } else {
                    break;
                }
            }
        }
    }

    return maxDistSq;
}

The solution defines the possible directions the robot can face using two arrays dx and dy. The direction is managed using a variable that cycles through the indices on executing turn commands. By maintaining a set of obstacles, it ensures efficient checks when the robot moves. The maximum squared distance is updated whenever the robot's position changes.

Complexity

Time Complexity: O(N + M), where N is the number of commands and M is the number of obstacles.
Space Complexity: O(M), where M is the number of obstacles.

Try this approach in the editor

Approach 2: Hash Table + Simulation

We define a direction array dirs = [0, 1, 0, -1, 0] of length 5, where each pair of adjacent elements represents a direction. That is, (dirs[0], dirs[1]) represents north, (dirs[1], dirs[2]) represents east, and so on.

We use a hash table s to store the coordinates of all obstacles, so we can determine in O(1) time whether the next step will encounter an obstacle.

Additionally, we use two variables x and y to represent the robot's current coordinates, initially x = y = 0. The variable k represents the robot's current direction, and the answer variable ans represents the maximum squared Euclidean distance from the origin.

Next, we iterate over each element c in the array commands:

  • If c = -2, the robot turns left 90 degrees, i.e., k = (k + 3) bmod 4;
  • If c = -1, the robot turns right 90 degrees, i.e., k = (k + 1) bmod 4;
  • Otherwise, the robot moves forward c units. We combine the robot's current direction k with the direction array dirs to obtain the increments along the x-axis and y-axis. We accumulate the increments step by step onto x and y, and check whether each new coordinate (nx, ny) is in the obstacle set. If not, we update the answer ans; otherwise, we stop the simulation and proceed to the next command.

Finally, return the answer ans.

The time complexity is O(C times n + m) and the space complexity is O(m), where C is the maximum number of steps per move, and n and m are the lengths of the arrays commands and obstacles, respectively.

function robotSim(commands: number[], obstacles: number[][]): number {
    const dirs = [0, 1, 0, -1, 0];
    const s: Set<number> = new Set();
    const f = (x: number, y: number) => x * 60010 + y;
    for (const [x, y] of obstacles) {
        s.add(f(x, y));
    }
    let [ans, x, y, k] = [0, 0, 0, 0];
    for (let c of commands) {
        if (c === -2) {
            k = (k + 3) % 4;
        } else if (c === -1) {
            k = (k + 1) % 4;
        } else {
            while (c-- > 0) {
                const [nx, ny] = [x + dirs[k], y + dirs[k + 1]];
                if (s.has(f(nx, ny))) {
                    break;
                }
                [x, y] = [nx, ny];
                ans = Math.max(ans, x * x + y * y);
            }
        }
    }
    return ans;
}
func robotSim(commands []int, obstacles [][]int) (ans int) {
	dirs := [5]int{0, 1, 0, -1, 0}
	type pair struct{ x, y int }
	s := map[pair]bool{}
	for _, e := range obstacles {
		s[pair{e[0], e[1]}] = true
	}
	var x, y, k int
	for _, c := range commands {
		if c == -2 {
			k = (k + 3) % 4
		} else if c == -1 {
			k = (k + 1) % 4
		} else {
			for ; c > 0 && !s[pair{x + dirs[k], y + dirs[k+1]}]; c-- {
				x += dirs[k]
				y += dirs[k+1]
				ans = max(ans, x*x+y*y)
			}
		}
	}
	return
}
use std::collections::HashSet;

impl Solution {
    pub fn robot_sim(commands: Vec<i32>, obstacles: Vec<Vec<i32>>) -> i32 {
        let dirs: [i32; 5] = [0, 1, 0, -1, 0];
        let mut s: HashSet<(i32, i32)> = HashSet::new();

        for o in obstacles {
            s.insert((o[0], o[1]));
        }

        let mut ans: i32 = 0;
        let mut k: i32 = 0;
        let mut x: i32 = 0;
        let mut y: i32 = 0;

        for c in commands {
            if c == -2 {
                k = (k + 3) % 4;
            } else if c == -1 {
                k = (k + 1) % 4;
            } else {
                for _ in 0..c {
                    let nx: i32 = x + dirs[k as usize];
                    let ny: i32 = y + dirs[k as usize + 1];

                    if s.contains(&(nx, ny)) {
                        break;
                    }

                    x = nx;
                    y = ny;
                    ans = ans.max(x * x + y * y);
                }
            }
        }

        ans
    }
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Simulate Robot Movement Using Direction Array

Time Complexity: O(N + M), where N is the number of commands and M is the number of obstacles.
Space Complexity: O(M), where M is the number of obstacles.

Hash Table + Simulation–

Complexity analysis

ApproachTimeSpaceWhen to Use
Naive Simulation with Obstacle ScanO(n * k)O(1)When obstacle count is very small or during initial brute-force reasoning
Direction Array + Hash Set SimulationO(n)O(k)General case. Fast obstacle lookup and clean movement simulation

Frequently asked questions

Is Walking Robot Simulation easy or hard?

Walking Robot Simulation is typically classified as a medium-level problem. The movement rules are simple, but the challenge is recognizing that obstacle checks must be optimized with a hash set and that directions should be managed using a compact array-based representation.

Walking Robot Simulation Python/Java solution

Implement the simulation by storing obstacles in a set and tracking the robot’s direction using an index over a direction array. Rotate left or right by adjusting the index with modulo arithmetic. For forward commands, move one step at a time and stop if the next coordinate is an obstacle.

How to solve Walking Robot Simulation in O(n)?

Convert the obstacle list into a hash set for constant-time lookups. Maintain a direction array representing north, east, south, and west. For each command, update the direction index for turns or move step-by-step while checking whether the next coordinate exists in the set. Track the maximum distance squared from the origin during movement.

What is the best approach for Walking Robot Simulation?

The most efficient approach uses a hash set to store obstacle coordinates and a direction array to manage robot orientation. Each forward command moves step-by-step while checking the next coordinate in O(1) time using the set. This keeps the simulation linear in the number of movement steps and avoids repeatedly scanning the obstacle list.

Is Walking Robot Simulation asked at Google/Amazon/Meta?

Simulation and grid movement problems like Walking Robot Simulation commonly appear in interviews at companies such as Amazon, Google, and Meta. They test ability to translate problem rules into code, manage coordinates, and optimize lookups with appropriate data structures.

What data structure is used in Walking Robot Simulation?

The key data structure is a hash set used to store obstacle coordinates. It enables O(1) average-time checks to determine whether the robot can move to the next grid cell. An array is also used to store direction vectors for north, east, south, and west.

What is the time complexity of Walking Robot Simulation?

Using the optimized hash set approach, the time complexity is O(n) where n is the total number of movement steps executed from the commands. Each step performs a constant-time obstacle lookup. Space complexity is O(k) to store k obstacle coordinates in the set.

Comments

Next problem · similarWalking Robot Simulation IIMedium
Now write it yourselfClose this page and solve Walking Robot Simulation in the editor, without looking.
Practise Walking Robot Simulation