#657

Easy

LeetCode Problem Workspace

Robot Return to Origin

Judge whether a robot returns to the origin after a sequence of moves using string manipulation and simulation.

Problem Statement

You are given a robot that starts at the position (0, 0) on a 2D plane. A string of moves, where each character represents a movement direction, tells you the robot's journey. Valid moves are 'R' for right, 'L' for left, 'U' for up, and 'D' for down.

Your goal is to determine whether the robot returns to the origin, (0, 0), after performing all the moves in the given string. If the robot ends up at (0, 0), return true; otherwise, return false.

Examples

Example 1

Input: moves = "UD"

Output: true

The robot moves up once, and then down once. All moves have the same magnitude, so it ended up at the origin where it started. Therefore, we return true.

Example 2

Input: moves = "LL"

Output: false

The robot moves left twice. It ends up two "moves" to the left of the origin. We return false because it is not at the origin at the end of its moves.

Constraints

1 <= moves.length <= 2 * 104
moves only contains the characters 'U', 'D', 'L' and 'R'.

Solution Approach

Count Move Occurrences

Count the occurrences of each move: 'R', 'L', 'U', and 'D'. The robot returns to the origin if the number of 'R' moves equals the number of 'L' moves, and the number of 'U' moves equals the number of 'D' moves. This provides an easy check if the horizontal and vertical movements cancel each other out.

Simulate the Movements

Another approach is to simulate the robot's movements. Start at (0, 0) and update the robot's position based on the move instructions. For each character in the string, adjust the x and y coordinates accordingly. After processing all the moves, check if the robot's position is still at (0, 0).

Time and Space Complexity

The solution can be solved in O(N) time where N is the length of the moves string. Since only a few variables are needed for tracking the robot’s position, the space complexity is O(1), making the solution both time and space efficient.

Complexity Analysis

Metric	Value
Time	O(N)
Space	O(1)

The time complexity is O(N) because each character in the string must be processed once. The space complexity is O(1) because only two integer variables are needed to track the robot's position.

What Interviewers Usually Probe

Assessing the candidate's ability to leverage string manipulations and simulation to solve problems.
Evaluating understanding of time and space complexities for simple movement-based problems.
Looking for the candidate's approach to validating edge cases like short or long strings.

Common Pitfalls or Variants

Common pitfalls

Not considering edge cases such as the smallest and largest strings.
Forgetting to check both horizontal and vertical moves when validating the return to origin.
Using unnecessary additional data structures or overcomplicating the solution with extra logic.

Follow-up variants

Change the plane size and test if the robot still returns to the origin.
Consider diagonal moves or moves that repeat multiple times.
Optimize for cases with very large strings, keeping performance in mind.

FAQ

How do I solve the Robot Return to Origin problem?

You can solve this problem by counting the occurrences of each move and checking if the horizontal and vertical movements cancel out.

What is the time complexity of the Robot Return to Origin solution?

The time complexity is O(N), where N is the length of the move sequence, because we need to process each move once.

How can I optimize the solution for large inputs in Robot Return to Origin?

The solution is already optimized with O(N) time and O(1) space complexity. You can further optimize by using a constant number of variables for tracking position.

Can you handle edge cases for Robot Return to Origin?

Yes, ensure to handle edge cases like a single move or a move sequence that doesn't cancel out, resulting in a false output.

What patterns are involved in solving the Robot Return to Origin?

This problem involves string manipulation and simulation to track the robot's position and validate if it returns to the origin.

terminal

Solution

Solution 1: Maintain Coordinates

We can maintain a coordinate $(x, y)$ to represent the robot's movement in the horizontal and vertical directions.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def judgeCircle(self, moves: str) -> bool:
        x = y = 0
        for c in moves:
            match c:
                case "U":
                    y += 1
                case "D":
                    y -= 1
                case "L":
                    x -= 1
                case "R":
                    x += 1
        return x == 0 and y == 0

Continue Practicing

#640 solve the equation #592 fraction addition and subtraction #537 complex number multiplication