Robot Return to Origin

Difficulty: Easy | Acceptance: 78.10% | Paid: No Topics: String, Simulation

There is a robot starting at the position (0, 0), the origin, on a 2D plane. Given a sequence of its moves, judge if this robot ends up at (0, 0) after it completes its moves.

You are given a string moves that represents the move sequence of the robot where move[i] represents its ith move. The valid moves are ‘R’ (right), ‘L’ (left), ‘U’ (up), and ‘D’ (down).

Return true if and only if the robot returns to the origin after it finishes all of its moves.

• Examples
• Constraints
• Simulation
• Counting

Examples

Input: moves = "UD"
Output: true
Explanation: 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.

Input: moves = "LL"
Output: false
Explanation: 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 * 10⁴
moves[i] is either 'U', 'D', 'L', or 'R'.

Simulation

Intuition We can simulate the robot’s movement on a 2D grid by tracking its x and y coordinates. For every move, we update the coordinates accordingly. If the final coordinates are (0, 0), the robot has returned to the origin.

Steps

• Initialize x and y coordinates to 0.
• Iterate through each character in the moves string.
• Update x or y based on the direction (U: y++, D: y—, R: x++, L: x—).
• After the loop, check if both x and y are 0.

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

Complexity

• Time: O(n) where n is the length of the string.
• Space: O(1) as we only use two variables for coordinates.
• Notes: This is the most intuitive approach and works efficiently within the constraints.

Counting

Intuition The robot returns to the origin if the number of ‘Up’ moves equals the number of ‘Down’ moves, and the number of ‘Right’ moves equals the number of ‘Left’ moves. We can count the occurrences of each character and compare the pairs.

Steps

• Count the occurrences of ‘U’, ‘D’, ‘L’, and ‘R’ in the string.
• Check if count(‘U’) == count(‘D’) and count(‘L’) == count(‘R’).
• Return true if both conditions are met, otherwise false.

class Solution:
    def judgeCircle(self, moves: str) -> bool:
        return moves.count('U') == moves.count('D') and moves.count('L') == moves.count('R')

Complexity

• Time: O(n) as we traverse the string to count characters.
• Space: O(1) if using simple counters, or O(n) in languages like JavaScript/TypeScript if using split (which creates an array), though the logical space complexity is constant.
• Notes: In Python, the built-in count method makes this very concise. In C++, std::count is efficient.