LeetCode 657 - Robot Return to Origin

LeetCode Problem 657

Difficulty: 🟢 Easy
Topics: String, Simulation

Solution

Problem Understanding

This problem asks us to determine whether a robot, starting at the origin (0, 0) on a 2D plane, returns to the origin after executing a sequence of moves. Each move is represented by a character in a string: 'R' moves right, 'L' moves left, 'U' moves up, and 'D' moves down. The robot always moves exactly one unit per step, and the direction it is "facing" does not matter.

The input is a single string moves of length up to 20,000. The output is a boolean: true if the robot ends at (0, 0) after all moves, false otherwise. Since the moves are constrained to these four characters and the string length is moderate, a linear-time algorithm is feasible.

Edge cases include the robot making only vertical moves without horizontal compensation, or only horizontal moves without vertical compensation. The problem guarantees that the string is non-empty and contains only valid moves, so we do not need to handle invalid input characters.

Approaches

The brute-force approach is straightforward: we simulate the robot's position step by step. Initialize coordinates (x, y) at (0, 0) and iterate through each move. For 'R' increment x, for 'L' decrement x, for 'U' increment y, and for 'D' decrement y. After processing all moves, check if (x, y) equals (0, 0). This works because the sum of opposite moves must cancel out for the robot to return to the origin.

The key insight for an optimal approach is that we only need to count the occurrences of opposite moves. The robot returns to the origin if and only if the number of 'L' moves equals the number of 'R' moves and the number of 'U' moves equals the number of 'D' moves. This allows a simple counting approach without tracking exact coordinates, but in practice, both approaches have the same time complexity. The counting approach may have slightly less bookkeeping.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(1)	Simulate coordinates step by step.
Counting	O(n)	O(1)	Count occurrences of each move type and compare opposites.

Algorithm Walkthrough

1. Initialize two variables x and y to 0, representing the robot's horizontal and vertical positions.
2. Iterate through each character in the string moves.
3. If the character is 'R', increment x. If it is 'L', decrement x.
4. If the character is 'U', increment y. If it is 'D', decrement y.
5. After processing all moves, check whether both x and y are 0.
6. Return true if (x, y) equals (0, 0), otherwise return false.

Why it works: Each move directly updates the robot's coordinates in a consistent way. Opposite moves cancel each other out, so the robot returns to the origin only if horizontal and vertical displacements sum to zero. This invariant guarantees correctness.

Python Solution

class Solution:
    def judgeCircle(self, moves: str) -> bool:
        x = 0
        y = 0
        for move in moves:
            if move == 'R':
                x += 1
            elif move == 'L':
                x -= 1
            elif move == 'U':
                y += 1
            elif move == 'D':
                y -= 1
        return x == 0 and y == 0

In this implementation, we initialize coordinates (x, y) at the origin and iterate through each move. Each move updates the corresponding coordinate. At the end, we return whether both coordinates are back to zero, which matches the algorithm walkthrough exactly.

Go Solution

func judgeCircle(moves string) bool {
    x, y := 0, 0
    for _, move := range moves {
        switch move {
        case 'R':
            x++
        case 'L':
            x--
        case 'U':
            y++
        case 'D':
            y--
        }
    }
    return x == 0 && y == 0
}

The Go solution mirrors the Python solution. We iterate over each rune in the string, using a switch statement to update x or y. There are no concerns about nil values since the input string is guaranteed to be valid and non-empty.

Worked Examples

Example 1: moves = "UD"

Move	x	y
U	0	1
D	0	0

Return value: true

Example 2: moves = "LL"

Move	x	y
L	-1	0
L	-2	0

Return value: false

Example 3: moves = "RRDDLU"

Move	x	y
R	1	0
R	2	0
D	2	-1
D	2	-2
L	1	-2
U	1	-1

Return value: false

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Iterate through the move string once, n = length of moves
Space	O(1)	Only two integer variables are used for coordinates

The algorithm is linear in time because each move is processed exactly once, and it uses constant space since we only track x and y.

Test Cases

# Provided examples
assert Solution().judgeCircle("UD") == True  # up then down cancels
assert Solution().judgeCircle("LL") == False  # moves left only

# Single move
assert Solution().judgeCircle("U") == False  # cannot return
assert Solution().judgeCircle("R") == False

# Balanced moves
assert Solution().judgeCircle("UDLR") == True  # all directions cancel
assert Solution().judgeCircle("UUDDLLRR") == True  # longer sequence balanced

# Edge cases with repeated unbalanced moves
assert Solution().judgeCircle("UUUU") == False
assert Solution().judgeCircle("RRRR") == False

# Mixed long sequence
assert Solution().judgeCircle("RULDRULDRULD") == True  # balanced sequence
assert Solution().judgeCircle("RULDRULDRUL") == False  # last move breaks balance

Test	Why
"UD"	Simple vertical cancellation
"LL"	Horizontal movement only, not returning
"U" / "R"	Single move, cannot return
"UDLR"	All directions cancel
"UUDDLLRR"	Longer sequence balanced
"UUUU" / "RRRR"	Repeated unbalanced moves
"RULDRULDRULD"	Mixed sequence returning
"RULDRULDRUL"	Mixed sequence not returning

Edge Cases

One important edge case is a single move. Since the robot moves one unit, it cannot return to the origin, and the function correctly returns false.

Another edge case is a perfectly balanced sequence where moves cancel each other, regardless of order. Our coordinate update method guarantees that the final coordinates will be (0, 0) if moves cancel.

A third edge case is a long unbalanced sequence. Even if there are many moves in one direction, the function will correctly compute the net displacement without overflow since Python integers are arbitrary-precision and Go integers are safe within the problem constraints.

This approach also handles sequences with only vertical or only horizontal moves, returning false when necessary.