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:

Move	Meaning
U	Move up
D	Move down
L	Move left
R	Move right

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

Otherwise, return False.

Input and Output

Item	Meaning
Input	A string moves
Output	True if the robot ends at (0, 0), otherwise False
Start position	(0, 0)
Movement size	Every move changes position by exactly one unit

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:

Variable	Meaning
x	Horizontal position
y	Vertical position

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:

Pair	Effect
U and D	Vertical movement cancels
L and R	Horizontal movement cancels

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:

Move	Position change
U	(x, y + 1)
D	(x, y - 1)
L	(x - 1, y)
R	(x + 1, y)

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

Metric	Value	Why
Time	O(n)	We process each move once
Space	O(1)	Only two integer variables are used

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:

Test	Why
"UD"	Simple canceling movement
"LL"	Ends away from origin
"URDL"	Square path returns to origin
""	No movement keeps robot at origin
"UUDDLLRR"	Multiple canceling moves
"UUDDL"	One extra move prevents return
"RRDD"	Different nonzero final position