Problem Description

The "Robot Return to Origin" problem asks whether a robot, starting at the coordinate (0, 0) on a 2D plane, will return to its original position after executing a sequence of moves. The moves are given as a string moves where each character is one of:

• 'U': move up (increase y by 1)
• 'D': move down (decrease y by 1)
• 'L': move left (decrease x by 1)
• 'R': move right (increase x by 1)

Key constraints:

• Each move is a single character in the set {'U', 'D', 'L', 'R'}.
• The robot must execute all moves in the order given.
• The robot starts at (0, 0).

Thought Process

To solve this problem, first consider the meaning of each move. Each move changes the robot's position by altering the x or y coordinate. The robot returns to the origin if, after all moves, both the x and y coordinates are zero.

A brute-force approach might be to simulate every move and track the position. However, since there are only four possible moves and the robot's position can be represented by two variables (x and y), this simulation is very straightforward and efficient.

To optimize, we recognize that each 'U' cancels a 'D', and each 'L' cancels a 'R'. Thus, if the number of 'U's equals the number of 'D's, and the number of 'L's equals the number of 'R's, the robot must return to the origin.

Solution Approach

The solution can be implemented in two main ways:

• Simulate Movement: Initialize x = 0 and y = 0. For each move, update x or y accordingly. At the end, check if both x and y are zero.
• Count Moves: Count the number of occurrences of each move ('U', 'D', 'L', 'R'). If count('U') == count('D') and count('L') == count('R'), return to origin.

1. Initialize variables to track the robot's position (x = 0, y = 0).
2. Iterate through each character in moves:
• If the character is 'U', increment y.
• If the character is 'D', decrement y.
• If the character is 'L', decrement x.
• If the character is 'R', increment x.
3. After all moves, check if both x and y are zero.
4. Return True if at the origin, False otherwise.

This approach is efficient because each move is processed in constant time, and no extra data structures are needed.

Example Walkthrough

Example Input: moves = "UDLR"

1. Start at (x, y) = (0, 0).
2. First move: 'U' → y = 1 ((0, 1)).
3. Second move: 'D' → y = 0 ((0, 0)).
4. Third move: 'L' → x = -1 ((-1, 0)).
5. Fourth move: 'R' → x = 0 ((0, 0)).
6. End at (0, 0). The robot returned to the origin. Return True.

Another Example: moves = "UUDDL"
Steps:

• 'U' → (0,1)
• 'U' → (0,2)
• 'D' → (0,1)
• 'D' → (0,0)
• 'L' → (-1,0)

Time and Space Complexity

Brute-force Approach:

• Time Complexity: O(n) where n is the length of moves, since we process each move once.
• Space Complexity: O(1) because we only use a fixed number of variables (x and y).

• Time Complexity: O(n), as we count occurrences in the string.
• Space Complexity: O(1), since we only store counts for four move types.

Both approaches are optimal for this problem, as every move must be considered.

Summary

The "Robot Return to Origin" problem is elegantly solved by tracking the robot's position as it processes each move. By recognizing that opposite moves cancel each other out, we can use simple counting or coordinate simulation to determine if the robot returns to the origin. The solution is efficient, requiring only a single pass through the input and constant extra space, making it both intuitive and optimal for this task.

Code Implementation

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

class Solution {
public:
    bool judgeCircle(string moves) {
        int x = 0, y = 0;
        for (char move : moves) {
            if (move == 'U') y++;
            else if (move == 'D') y--;
            else if (move == 'L') x--;
            else if (move == 'R') x++;
        }
        return x == 0 && y == 0;
    }
};
      

class Solution {
    public boolean judgeCircle(String moves) {
        int x = 0, y = 0;
        for (char move : moves.toCharArray()) {
            if (move == 'U') y++;
            else if (move == 'D') y--;
            else if (move == 'L') x--;
            else if (move == 'R') x++;
        }
        return x == 0 && y == 0;
    }
}
      

var judgeCircle = function(moves) {
    let x = 0, y = 0;
    for (let move of moves) {
        if (move === 'U') y++;
        else if (move === 'D') y--;
        else if (move === 'L') x--;
        else if (move === 'R') x++;
    }
    return x === 0 && y === 0;
};