Walking Robot Simulation II

Med

#1884Time: O(num) for each call to `step(num)`. Since `num` can be up to 10<sup>5</sup>, this is inefficient.Space: O(1) - We only store a few variables for the robot's state.1 company

Patterns

Design

Companies

Block

Prompt

A width x height grid is on an XY-plane with the bottom-left cell at (0, 0) and the top-right cell at (width - 1, height - 1). The grid is aligned with the four cardinal directions ("North", "East", "South", and "West"). A robot is initially at cell (0, 0) facing direction "East".

The robot can be instructed to move for a specific number of steps. For each step, it does the following.

Attempts to move forward one cell in the direction it is facing.
If the cell the robot is moving to is out of bounds, the robot instead turns 90 degrees counterclockwise and retries the step.

After the robot finishes moving the number of steps required, it stops and awaits the next instruction.

Implement the Robot class:

Robot(int width, int height) Initializes the width x height grid with the robot at (0, 0) facing "East".
void step(int num) Instructs the robot to move forward num steps.
int[] getPos() Returns the current cell the robot is at, as an array of length 2, [x, y].
String getDir() Returns the current direction of the robot, "North", "East", "South", or "West".

Example 1:

Input
["Robot", "step", "step", "getPos", "getDir", "step", "step", "step", "getPos", "getDir"]
[[6, 3], [2], [2], [], [], [2], [1], [4], [], []]
Output
[null, null, null, [4, 0], "East", null, null, null, [1, 2], "West"]

Explanation
Robot robot = new Robot(6, 3); // Initialize the grid and the robot at (0, 0) facing East.
robot.step(2);  // It moves two steps East to (2, 0), and faces East.
robot.step(2);  // It moves two steps East to (4, 0), and faces East.
robot.getPos(); // return [4, 0]
robot.getDir(); // return "East"
robot.step(2);  // It moves one step East to (5, 0), and faces East.
                // Moving the next step East would be out of bounds, so it turns and faces North.
                // Then, it moves one step North to (5, 1), and faces North.
robot.step(1);  // It moves one step North to (5, 2), and faces North (not West).
robot.step(4);  // Moving the next step North would be out of bounds, so it turns and faces West.
                // Then, it moves four steps West to (1, 2), and faces West.
robot.getPos(); // return [1, 2]
robot.getDir(); // return "West"

Constraints:

2 <= width, height <= 100
1 <= num <= 10⁵
At most 10⁴ calls in total will be made to step, getPos, and getDir.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly translates the problem description into code. It simulates the robot's movement one step at a time. For each of the num steps, it calculates the next position. If the move is valid, the robot moves. If the move is out of bounds, the robot turns 90 degrees counter-clockwise and attempts to move again in the new direction, all within the same single step count. This process is repeated for all num steps.

Algorithm

Initialize the robot's state: x=0, y=0, dir=0 (for East), width, and height.
Create helper arrays for movement, e.g., dx = {1, 0, -1, 0} and dy = {0, 1, 0, -1} for directions East, North, West, South.
Implement the step(num) method: a. Loop num times, from i = 0 to num - 1. b. In each iteration, simulate one step. This step might involve turns. c. Use an inner while(true) loop to handle the "retry the step" logic. d. Calculate the next potential position (nx, ny). e. If (nx, ny) is within the grid boundaries, update the robot's position (x, y) and break the inner while loop. f. If (nx, ny) is out of bounds, update the direction (turn 90 degrees counter-clockwise) and continue the inner while loop to retry the step with the new direction.
Implement getPos() to return the current [x, y].
Implement getDir() to return the string corresponding to the current direction.

Walkthrough

The state of the robot is maintained using its coordinates (x, y) and its current direction dir. We can represent the four cardinal directions numerically (e.g., 0 for East, 1 for North, 2 for West, 3 for South). Helper arrays dx and dy can store the change in x and y for each direction.

The step(num) method contains a main loop that iterates num times. Inside this loop, a nested while(true) loop handles a single step. This inner loop is necessary because a single step might require the robot to turn multiple times if it's in a corner before it can make a valid move. For instance, if the robot is at (width-1, height-1) facing North, it will turn West, then South, before it can move one step to (width-1, height-2).

1class Robot {2    int width, height;3    int x, y, dir;4    // directions: 0:East, 1:North, 2:West, 3:South5    int[][] moves = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};6    String[] dirStrings = {"East", "North", "West", "South"};7 8    public Robot(int width, int height) {9        this.width = width;10        this.height = height;11        this.x = 0;12        this.y = 0;13        this.dir = 0; // Start facing East14    }15 16    public void step(int num) {17        for (int i = 0; i < num; i++) {18            // This inner loop handles one step, which may include turns.19            while (true) {20                int nextX = x + moves[dir][0];21                int nextY = y + moves[dir][1];22 23                if (nextX >= 0 && nextX < width && nextY >= 0 && nextY < height) {24                    x = nextX;25                    y = nextY;26                    break; // Step successfully completed27                } else {28                    // Hit a boundary, turn counter-clockwise and retry the step.29                    dir = (dir + 1) % 4;30                }31            }32        }33    }34 35    public int[] getPos() {36        return new int[]{x, y};37    }38 39    public String getDir() {40        return dirStrings[dir];41    }42}

Complexity

Time

O(num) for each call to `step(num)`. Since `num` can be up to 10<sup>5</sup>, this is inefficient.

Space

O(1) - We only store a few variables for the robot's state.

Trade-offs

Pros

It is simple to conceptualize and implement.
It correctly follows the logic described in the problem statement.

Cons

This approach is too slow for large values of num as its time complexity is directly proportional to the number of steps.
It will likely result in a 'Time Limit Exceeded' (TLE) error on platforms with strict time constraints.

This approach significantly optimizes the simulation by understanding the robot's movement pattern. The robot is always confined to the grid's boundary. This boundary forms a closed loop or a cycle. The key insight is that the robot's state (position and direction) is periodic with respect to the number of steps. The length of this perimeter cycle is P = 2 * (width + height - 2). Instead of simulating a large number of steps num, we can use the modulo operator (num % P) to find the equivalent smaller number of steps that result in the same final state. This reduces the number of simulation steps to at most P-1, making the step function's complexity independent of num.

Algorithm

Observe that the robot always moves along the perimeter of the grid. The total length of this perimeter path is P = 2 * (width - 1) + 2 * (height - 1).
Any movement of P steps from any point on the perimeter cycle brings the robot back to the same position with the same orientation. The only exception is the initial state (0,0) facing East, which is not part of the main cycle.
In step(num), we can optimize by realizing that only the remainder of num divided by P matters for the final position. So, we can update num = num % P.
A special case arises if num is a multiple of P. If the robot is in its initial state (0,0) East, a move of P steps will place it at (0,0) but facing South. If it's at any other state, it returns to the same state. We handle this by checking if num becomes 0 after the modulo operation.
After reducing num, we perform the simulation for the remaining (at most P-1) steps using the same step-by-step logic as the brute-force approach. Since P is small (<= 792), this is very fast.

Walkthrough

The state of the robot (x, y, dir) is maintained as in the brute-force approach. The step(num) method is where the optimization occurs.

First, we calculate the perimeter P = 2 * (width + height - 2). If the perimeter is greater than 0, we can reduce num by taking num = num % P.

There's a crucial edge case: what if num is a multiple of the perimeter? In this case, num % P becomes 0. If the robot starts at its initial state (0,0) facing East, a move of P steps lands it at (0,0) facing South. For any other state on the perimeter, a move of P steps brings it back to the exact same state (position and direction). We handle this by checking if x=0, y=0, dir=0 when the effective number of steps is 0. If so, we just update the direction to South.

After this initial optimization, the remaining number of steps is at most P-1. We can then simulate these remaining steps using the simple and reliable step-by-step logic from the first approach. Since width and height are at most 100, P is at most 792, so the simulation loop runs a small, constant number of times.

1class Robot {2    int width, height;3    int x, y, dir;4    int[][] moves = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};5    String[] dirStrings = {"East", "North", "West", "South"};6 7    public Robot(int width, int height) {8        this.width = width;9        this.height = height;10        this.x = 0;11        this.y = 0;12        this.dir = 0; // East13    }14 15    public void step(int num) {16        int perimeter = 2 * (width + height - 2);17        if (perimeter > 0) {18            num %= perimeter;19        }20 21        // If num is 0, we don't move. However, if the original num was a multiple of the perimeter22        // and we are at the initial state, the direction changes.23        if (num == 0 && this.x == 0 && this.y == 0 && this.dir == 0) {24            this.dir = 3; // Becomes South25            return;26        }27 28        for (int i = 0; i < num; i++) {29            int nextX = x + moves[dir][0];30            int nextY = y + moves[dir][1];31 32            while (nextX < 0 || nextX >= width || nextY < 0 || nextY >= height) {33                dir = (dir + 1) % 4;34                nextX = x + moves[dir][0];35                nextY = y + moves[dir][1];36            }37            x = nextX;38            y = nextY;39        }40    }41 42    public int[] getPos() {43        return new int[]{x, y};44    }45 46    public String getDir() {47        return dirStrings[dir];48    }49}

Complexity

Time

O(width + height) for each call to `step(num)`. The number of iterations is bounded by the perimeter `P`, which is `O(width + height)`. This is effectively constant time as `width` and `height` are small.

Space

O(1) - We only store a few variables for the robot's state.

Trade-offs

Pros

Extremely efficient, with a constant time complexity for the step method regardless of num.
Easily passes all time constraints.

Cons

The logic involving modulo arithmetic and handling the special initial state can be tricky to get right.
Requires careful analysis of the robot's movement patterns.

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem