LeetCode 657: Robot Return to Origin

Problem Restatement

A robot starts at position:

(0, 0)

We are given a string called moves.

Each character tells the robot to move one step:

After executing all moves, return True if the robot returns to the origin (0, 0).

Otherwise, return False.

Input and Output

Example function shape:

def judgeCircle(moves: str) -> bool:
    ...

Examples

Consider:

moves = "UD"

The robot moves:

1. Up to (0, 1)
2. Down back to (0, 0)

The final position is the origin.

So the answer is:

True

Another example:

moves = "LL"

The robot moves:

1. Left to (-1, 0)
2. Left to (-2, 0)

The final position is not the origin.

So the answer is:

False

Another example:

moves = "URDL"

The robot moves in a square:

(0,0)
 -> (0,1)
 -> (1,1)
 -> (1,0)
 -> (0,0)

The robot returns to the origin.

So the answer is:

True

First Thought: Simulate the Movement

The robot position changes after every move.

So we can directly simulate the process.

Keep track of:

Then scan the string one character at a time.

Each move updates either x or y.

At the end, the robot returns to the origin exactly when:

x == 0 and y == 0

Key Insight

Each pair of opposite moves cancels out.

For example:

So the robot returns to the origin if:

number of U moves == number of D moves

and:

number of L moves == number of R moves

The simulation approach naturally checks this.

Algorithm

1. Start with:

x = 0
y = 0

2. For each character in moves:

   • U increases y
   • D decreases y
   • L decreases x
   • R increases x

3. After processing all moves:

   • Return whether (x, y) equals (0, 0)

Correctness

The variables x and y always represent the robot’s current position.

Initially, the robot starts at (0, 0).

Each move updates the position exactly according to the problem rules:

Therefore, after processing all characters, (x, y) is the robot’s final position.

The robot returns to the origin exactly when both coordinates are zero.

So returning:

x == 0 and y == 0

is correct.

Complexity

Here, n is the length of moves.

Implementation

class Solution:
    def judgeCircle(self, moves: str) -> bool:
        x = 0
        y = 0

        for move in moves:
            if move == "U":
                y += 1
            elif move == "D":
                y -= 1
            elif move == "L":
                x -= 1
            else:
                x += 1

        return x == 0 and y == 0

Code Explanation

We begin at the origin:

x = 0
y = 0

Then we scan the moves string:

for move in moves:

For each character, we update the coordinates.

Moving up increases the vertical position:

if move == "U":
    y += 1

Moving down decreases the vertical position:

elif move == "D":
    y -= 1

Moving left decreases the horizontal position:

elif move == "L":
    x -= 1

Otherwise, the move must be R:

else:
    x += 1

Finally, we check whether the robot returned to the origin:

return x == 0 and y == 0

Testing

def run_tests():
    s = Solution()

    assert s.judgeCircle("UD") is True
    assert s.judgeCircle("LL") is False
    assert s.judgeCircle("URDL") is True
    assert s.judgeCircle("") is True
    assert s.judgeCircle("UUDDLLRR") is True
    assert s.judgeCircle("UUDDL") is False
    assert s.judgeCircle("RRDD") is False

    print("all tests passed")

run_tests()

Test meaning: