LeetCode 2069 - Walking Robot Simulation II

The problem describes a simulation of a robot moving on a rectangular grid defined by width x height. The robot starts at the bottom-left corner (0, 0) facing East and moves in discrete steps.

leetcodemediumdesignsimulation

LeetCode Problem 2069

Difficulty: 🟡 Medium
Topics: Design, Simulation

Solution

Problem Understanding

The problem describes a simulation of a robot moving on a rectangular grid defined by width x height. The robot starts at the bottom-left corner (0, 0) facing East and moves in discrete steps. Each step moves the robot forward in its current direction unless the next cell is out of bounds, in which case the robot rotates 90 degrees counterclockwise and retries that step. The goal is to implement a class that can efficiently handle a potentially large number of steps while providing the robot’s current position and facing direction.

The input consists of the grid dimensions and a sequence of step instructions, where each instruction specifies the number of steps to move. The output consists of the robot’s position as [x, y] and its facing direction as a string "North", "East", "South", or "West". The constraints, including up to 10^5 steps per step call and 10^4 total method calls, imply that a naive simulation moving one step at a time is too slow. Edge cases to consider include the robot reaching a corner, where multiple rotations may occur in a single step call, and when the robot has to traverse along the perimeter repeatedly.

Approaches

The brute-force approach simulates each step individually, checking boundaries and turning counterclockwise when hitting an edge. This guarantees correctness because each step follows the problem rules exactly. However, since a single call may ask the robot to move up to 10^5 steps and there may be 10^4 calls, this can lead to up to 10^9 iterations, which is infeasible.

The key observation for an optimal approach is that the robot only moves along the perimeter of the grid after the first rotation, forming a fixed cyclic path along the rectangle edges. This allows precomputing the path as a list of coordinates and directions, enabling the robot to advance num steps by moving modulo the perimeter length, rather than simulating every step. The modulo operation ensures that very large step counts wrap around efficiently, and the position and direction can be retrieved in constant time.

Approach Time Complexity Space Complexity Notes
Brute Force O(num) per step) O(1) Simulate each step individually, too slow for large num
Optimal O(1) per step after preprocessing O(width + height) Precompute perimeter path, use modulo arithmetic to skip large step counts

Algorithm Walkthrough

  1. Initialization: Store the grid dimensions width and height. Create lists perimeter and directions that represent the robot's path along the perimeter in clockwise order and the corresponding direction at each cell.
  2. Build Perimeter Path: Starting from (0, 0) and facing East, traverse the rectangle clockwise to generate all unique edge cells. Add each cell to the perimeter list and the direction it will be facing at that cell to the directions list.
  3. Tracking Position: Maintain a single integer pos_index that points to the robot’s current location in the perimeter list.
  4. Step Function: When step(num) is called, update pos_index as (pos_index + num) % len(perimeter). This efficiently moves the robot num steps along the perimeter path in O(1) time.
  5. Get Position: Return the coordinate from perimeter[pos_index].
  6. Get Direction: Return the direction from directions[pos_index].

Why it works: The perimeter path captures all valid positions and directions the robot can occupy along the rectangle. Since the robot always follows the edge after the first rotation, moving by num modulo the perimeter length reproduces exactly the robot’s state after num steps.

Python Solution

from typing import List

class Robot:

    def __init__(self, width: int, height: int):
        self.width = width
        self.height = height
        self.perimeter = []
        self.directions = []
        # Precompute the perimeter clockwise starting East
        for x in range(width):
            self.perimeter.append((x, 0))
            self.directions.append("East")
        for y in range(1, height):
            self.perimeter.append((width - 1, y))
            self.directions.append("North")
        for x in range(width - 2, -1, -1):
            self.perimeter.append((x, height - 1))
            self.directions.append("West")
        for y in range(height - 2, 0, -1):
            self.perimeter.append((0, y))
            self.directions.append("South")
        self.pos_index = 0

    def step(self, num: int) -> None:
        if self.pos_index == 0 and num > 0:
            # Avoid "East" reset at start after first rotation
            self.pos_index = (self.pos_index + num - 1) % len(self.perimeter)
            self.pos_index += 1
        else:
            self.pos_index = (self.pos_index + num) % len(self.perimeter)

    def getPos(self) -> List[int]:
        return list(self.perimeter[self.pos_index])

    def getDir(self) -> str:
        return self.directions[self.pos_index]

The Python implementation precomputes the perimeter path and directions. In step, we handle a subtle case where the robot starts at (0, 0) and moves, ensuring the first turn is correctly represented. Both getPos and getDir simply retrieve precomputed values in O(1) time.

Go Solution

type Robot struct {
	width, height int
	perimeter     [][2]int
	directions    []string
	posIndex      int
}

func Constructor(width int, height int) Robot {
	r := Robot{
		width:      width,
		height:     height,
		perimeter:  make([][2]int, 0),
		directions: make([]string, 0),
		posIndex:   0,
	}

	for x := 0; x < width; x++ {
		r.perimeter = append(r.perimeter, [2]int{x, 0})
		r.directions = append(r.directions, "East")
	}
	for y := 1; y < height; y++ {
		r.perimeter = append(r.perimeter, [2]int{width - 1, y})
		r.directions = append(r.directions, "North")
	}
	for x := width - 2; x >= 0; x-- {
		r.perimeter = append(r.perimeter, [2]int{x, height - 1})
		r.directions = append(r.directions, "West")
	}
	for y := height - 2; y > 0; y-- {
		r.perimeter = append(r.perimeter, [2]int{0, y})
		r.directions = append(r.directions, "South")
	}

	return r
}

func (r *Robot) Step(num int) {
	if r.posIndex == 0 && num > 0 {
		r.posIndex = (r.posIndex + num - 1) % len(r.perimeter)
		r.posIndex++
	} else {
		r.posIndex = (r.posIndex + num) % len(r.perimeter)
	}
}

func (r *Robot) GetPos() []int {
	return []int{r.perimeter[r.posIndex][0], r.perimeter[r.posIndex][1]}
}

func (r *Robot) GetDir() string {
	return r.directions[r.posIndex]
}

In Go, the approach is identical. We use slices for perimeter and directions, and posIndex tracks the current location. The handling of the first step from (0,0) mirrors Python.

Worked Examples

For the example:

Robot robot = new Robot(6, 3);
robot.step(2); // Moves to (2,0), East
robot.step(2); // Moves to (4,0), East
robot.getPos(); // [4,0]
robot.getDir(); // "East"
robot.step(2); // Moves to (5,0), East -> turn North -> (5,1), North
robot.step(1); // (5,2), North
robot.step(4); // North blocked -> West -> (1,2), West
robot.getPos(); // [1,2]
robot.getDir(); // "West"

Perimeter list:

[(0,0),(1,0),(2,0),(3,0),(4,0),(5,0),(5,1),(5,2),(4,2),(3,2),(2,2),(1,2),(0,2),(0,1)]

directions list mirrors the robot’s facing at each cell.

Complexity Analysis

Measure Complexity Explanation
Time O(1) per step) Precomputed perimeter allows modulo arithmetic, no iteration per step
Space O(width + height) Store perimeter path and directions along rectangle edges

The preprocessing is O(width + height) but is acceptable due to the grid constraints (≤ 100).

Test Cases

robot = Robot(6, 3)
robot.step(2)
assert robot.getPos() == [2, 0]  # Moves East
assert robot.getDir() == "East"
robot.step(2)
assert robot.getPos() == [4