Scale Engineer

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.

  1. Attempts to move forward one cell in the direction it is facing.
  2. 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:

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 <= 105
  • At most 104 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

  1. Initialize the robot's state: x=0, y=0, dir=0 (for East), width, and height.
  2. Create helper arrays for movement, e.g., dx = {1, 0, -1, 0} and dy = {0, 1, 0, -1} for directions East, North, West, South.
  3. 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.
  4. Implement getPos() to return the current [x, y].
  5. 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).

class Robot {    int width, height;    int x, y, dir;    // directions: 0:East, 1:North, 2:West, 3:South    int[][] moves = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};    String[] dirStrings = {"East", "North", "West", "South"};     public Robot(int width, int height) {        this.width = width;        this.height = height;        this.x = 0;        this.y = 0;        this.dir = 0; // Start facing East    }     public void step(int num) {        for (int i = 0; i < num; i++) {            // This inner loop handles one step, which may include turns.            while (true) {                int nextX = x + moves[dir][0];                int nextY = y + moves[dir][1];                 if (nextX >= 0 && nextX < width && nextY >= 0 && nextY < height) {                    x = nextX;                    y = nextY;                    break; // Step successfully completed                } else {                    // Hit a boundary, turn counter-clockwise and retry the step.                    dir = (dir + 1) % 4;                }            }        }    }     public int[] getPos() {        return new int[]{x, y};    }     public String getDir() {        return dirStrings[dir];    }}

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.

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 →

Next problem