Robot Return to Origin

Easy
1744.

Robot Return to Origin

Robot Return to Origin is an easy coding problem on strings and simulation, asked in Amazon, Google and Microsoft interviews.

A robot starts at the origin (0, 0) of a grid. The string moves lists its moves in order: 'U' (up), 'D' (down), 'L' (left) and 'R' (right), each of exactly one unit.

Return true if the robot is back at the origin after the last move, and false otherwise. Which way the robot faces does not matter.

Example 1

Input
moves = "UD"
Output
true
Explanation
One step up, one step down.

Example 2

Input
moves = "LL"
Output
false
Explanation
The robot ends two units left of the origin.

Example 3

Input
moves = "RRDLUL"
Output
true

Constraints

  • 1 <= moves.length <= 2 * 10^4
  • moves only contains the characters 'U', 'D', 'L' and 'R'
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} moves
 * @return {boolean}
 */
var judgeCircle = function(moves) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Robot Return to Origin — Solution in Python, Java & C++

Robot Return to Origin solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Robot Return to Origin is an easy coding problem on strings and simulation, asked in Amazon, Google and Microsoft interviews.

  • Difficulty: Easy
  • Topics: Strings, Simulation
  • Asked at: Amazon, Google, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A robot starts at the origin (0, 0) of a grid. The string moves lists its moves in order: 'U' (up), 'D' (down), 'L' (left) and 'R' (right), each of exactly one unit.

Return true if the robot is back at the origin after the last move, and false otherwise. Which way the robot faces does not matter.

Example 1

Input: moves = "UD"
Output: true
Explanation: One step up, one step down.

Example 2

Input: moves = "LL"
Output: false
Explanation: The robot ends two units left of the origin.

Example 3

Input: moves = "RRDLUL"
Output: true

Constraints

  • 1 <= moves.length <= 2 * 10^4
  • moves only contains the characters 'U', 'D', 'L' and 'R'

Hints for Robot Return to Origin

  1. Hint 1

    Only the final position matters, not the path.

  2. Hint 2

    Track the horizontal and vertical offsets separately.

  3. Hint 3

    The robot is home exactly when the number of U equals the number of D and the number of L equals the number of R.

How to solve Robot Return to Origin

The moves commute: the final position is (#R − #L, #U − #D), whatever the order.

Approach

  1. Keep x = y = 0.
  2. For each move, adjust x for L/R and y for U/D.
  3. Return whether x == 0 and y == 0.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Both coordinates must be zero — balancing only U/D is not enough.

Reference solution

Python

def judgeCircle(moves: str) -> bool:
    return moves.count("U") == moves.count("D") and moves.count("L") == moves.count("R")

Java

public static boolean judgeCircle(String moves) {
    int x = 0, y = 0;
    for (int i = 0; i < moves.length(); i++) {
        char c = moves.charAt(i);
        if (c == 'U') y++;
        else if (c == 'D') y--;
        else if (c == 'L') x--;
        else x++;
    }
    return x == 0 && y == 0;
}

C++

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

JavaScript

var judgeCircle = function(moves) {
    var x = 0, y = 0;
    for (var i = 0; i < moves.length; i++) {
        var c = moves[i];
        if (c === "U") y++;
        else if (c === "D") y--;
        else if (c === "L") x--;
        else x++;
    }
    return x === 0 && y === 0;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings