2069. Walking Robot Simulation II

Design
Simulation

TIME

O(1) per operation

SPACE

O(1)

Intuition

The robot only walks along the perimeter of the grid. Use modular arithmetic to handle large step counts efficiently, then convert the perimeter index to coordinates and direction.

Solution

Key Insight: Perimeter Walking

The robot traces the perimeter:

Bottom edge: (0,0) → (w-1,0)      [East]
Right edge:  (w-1,0) → (w-1,h-1)  [North]
Top edge:    (w-1,h-1) → (0,h-1)  [West]
Left edge:   (0,h-1) → (0,0)      [South]

Perimeter length = 2 * (width + height - 2)

Step Optimization

Instead of simulating each step:

Track position as index along perimeter
index = (index + num) % perimeter
Convert index back to (x, y) and direction

Index to Position Conversion

Given perimeter index i:

i < width: Bottom edge → (i, 0), East
i < width + height - 1: Right edge → (width-1, i - width + 1), North
i < 2*width + height - 2: Top edge → (2*width + height - 3 - i, height-1), West
Otherwise: Left edge → (0, perimeter - i), South

Edge Case: Origin After Full Cycle

When robot returns to (0, 0) after moving (not initially), it faces "South" (came from left edge), not "East".

Complexity

Time: O(1) per operation
Space: O(1)

Edge Cases

Large num values → use modulo
Robot at corner → direction based on edge it's on
Multiple full perimeter cycles

Code

class Robot:
    """
    2069. Walking Robot Simulation II
    Time: O(1) per operation
    Space: O(1)
    """

    def __init__(self, width: int, height: int):
        self.width = width
        self.height = height
        self.perimeter = 2 * (width + height - 2)
        self.index = 0
        self.moved = False

    def step(self, num: int) -> None:
        self.index = (self.index + num) % self.perimeter
        self.moved = True

    def getPos(self) -> list[int]:
        i = self.index
        w, h = self.width, self.height

        if i < w:
            return [i, 0]
        i -= w - 1
        if i < h:
            return [w - 1, i]
        i -= h - 1
        if i < w:
            return [w - 1 - i, h - 1]
        i -= w - 1
        return [0, h - 1 - i]

    def getDir(self) -> str:
        i = self.index
        w, h = self.width, self.height

        if i == 0:
            return "South" if self.moved else "East"
        if i < w:
            return "East"
        if i < w + h - 1:
            return "North"
        if i < 2 * w + h - 2:
            return "West"
        return "South"

/**
 * 2069. Walking Robot Simulation II
 * Time: O(1) per operation
 * Space: O(1)
 */
class Robot {
    private int width, height;
    private int perimeter;
    private int index;
    private boolean moved;

    public Robot(int width, int height) {
        this.width = width;
        this.height = height;
        this.perimeter = 2 * (width + height - 2);
        this.index = 0;
        this.moved = false;
    }

    public void step(int num) {
        index = (index + num) % perimeter;
        moved = true;
    }

    public int[] getPos() {
        int i = index;
        int w = width, h = height;

        if (i < w) {
            return new int[]{i, 0};
        }
        i -= w - 1;
        if (i < h) {
            return new int[]{w - 1, i};
        }
        i -= h - 1;
        if (i < w) {
            return new int[]{w - 1 - i, h - 1};
        }
        i -= w - 1;
        return new int[]{0, h - 1 - i};
    }

    public String getDir() {
        int i = index;
        int w = width, h = height;

        if (i == 0) {
            return moved ? "South" : "East";
        }
        if (i < w) {
            return "East";
        }
        if (i < w + h - 1) {
            return "North";
        }
        if (i < 2 * w + h - 2) {
            return "West";
        }
        return "South";
    }
}