We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Robot Return to Origin

Number: 657

Difficulty: Easy

Paid? No

Companies: Google, Goldman Sachs, Yandex, Microsoft

Problem Description

A robot starts at the origin (0, 0) on a 2D plane and moves according to a given sequence represented by a string. Each character in the string corresponds to one move: 'R' (right), 'L' (left), 'U' (up), and 'D' (down). The task is to determine if the robot returns to the origin after executing all moves.

Key Insights

  • The robot's final position is determined by the net effect of all moves.
  • Moving right ('R') increases the x-coordinate, while left ('L') decreases it.
  • Moving up ('U') increases the y-coordinate, while down ('D') decreases it.
  • To return to the origin, the number of 'R' moves must equal the number of 'L' moves and the number of 'U' moves must equal the number of 'D' moves.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the moves string, as we need to traverse the string once. Space Complexity: O(1), since only a fixed amount of extra space is used for coordinates.

Solution

We can solve the problem by simulating the moves on a 2D plane using two variables, x and y, to track the robot's current coordinates. For each character in the moves string, update the coordinates accordingly:

  • 'R': Increment x by 1.
  • 'L': Decrement x by 1.
  • 'U': Increment y by 1.
  • 'D': Decrement y by 1. After processing all moves, check if both x and y are 0. If yes, the robot returns to the origin; otherwise, it does not.

Code Solutions

# Python solution for Robot Return to Origin

def judgeCircle(moves: str) -> bool:
    # Initialize coordinates at origin (0, 0)
    x, y = 0, 0
    # Process each move in the string
    for move in moves:
        if move == 'R':  # Move right increases x-coordinate
            x += 1
        elif move == 'L':  # Move left decreases x-coordinate
            x -= 1
        elif move == 'U':  # Move up increases y-coordinate
            y += 1
        elif move == 'D':  # Move down decreases y-coordinate
            y -= 1
    # Check if robot returned to origin
    return x == 0 and y == 0

# Example usage
moves = "UD"
print(judgeCircle(moves))  # Expected output: True
← Back to All Questions