657. Robot Return to Origin

LeetCode problem link (opens new window)

A robot is initially located at the origin (0, 0) on a 2D plane. It is given a sequence of its moves, and you need to check if the robot returns to the origin after completing all its movements.

The move sequence is represented as a string. Character move[i] represents its ith move. The robot's valid moves are R (right), L (left), U (up), and D (down). If the robot returns to the origin after completing all moves, return true; otherwise, return false.

Note: The "facing" direction of the robot is irrelevant. "R" will always make the robot move one unit to the right; "L" will always make it move left; similarly for "U" and "D". Assuming every movement of the robot is of the same magnitude.

Example

Example 1:

• Input: "UD"
• Output: true
• Explanation: The robot moves up once, and then moves down once. All movements are of the same magnitude, thus it ends up at its starting origin. Therefore, we return true.

Example 2:

• Input: "LL"
• Output: false
• Explanation: The robot moves left twice. It eventually ends up to the left of the origin, two "moves" away from it. We return false because it is not at the origin when the movements end.

Solution

This problem is fairly simple and doesn't require complex approaches like hashing or graph algorithms.

Just initialize x and y coordinates to 0, and then:

• if (moves[i] == 'U') y++;
• if (moves[i] == 'D') y--;
• if (moves[i] == 'L') x--;
• if (moves[i] == 'R') x++;

Finally, check if (x, y) has returned to the origin (0, 0).

As illustrated in the diagram:

C++ code:

class Solution {
public:
    bool judgeCircle(string moves) {
        int x = 0, y = 0;
        for (int i = 0; i < moves.size(); i++) {
            if (moves[i] == 'U') y++;
            if (moves[i] == 'D') y--;
            if (moves[i] == 'L') x--;
            if (moves[i] == 'R') x++;
        }
        if (x == 0 && y == 0) return true;
        return false;
    }
};

Other Language Versions

Java

// Time complexity: O(n)
// Space complexity: If using toCharArray, then it's O(n); if using charAt, then it's O(1).
class Solution {
    public boolean judgeCircle(String moves) {
        int x = 0;
        int y = 0;
        for (char c : moves.toCharArray()) {
            if (c == 'U') y++;
            if (c == 'D') y--;
            if (c == 'L') x++;
            if (c == 'R') x--;
        }
        return x == 0 && y == 0;
    }
}

Python

# Time complexity: O(n)
# Space complexity: O(1)
class Solution:
    def judgeCircle(self, moves: str) -> bool:
        x = 0  # Track current position
        y = 0
        for i in range(len(moves)):
            if (moves[i] == 'U'):
                y += 1
            if (moves[i] == 'D'):
                y -= 1
            if (moves[i] == 'L'):
                x += 1
            if (moves[i] == 'R'):
                x -= 1
        return x == 0 and y == 0

Go

func judgeCircle(moves string) bool {
    x := 0
    y := 0
    for i := 0; i < len(moves); i++ {
        if moves[i] == 'U' {
            y++
        }
        if moves[i] == 'D' {
            y--
        }
        if moves[i] == 'L' {
            x++
        }
        if moves[i] == 'R' {
            x--
        }
    }
    return x == 0 && y == 0
}

JavaScript

// Time complexity: O(n)
// Space complexity: O(1)
var judgeCircle = function(moves) {
    var x = 0; // Track current position
    var y = 0;
    for (var i = 0; i < moves.length; i++) {
        if (moves[i] == 'U') y++;
        if (moves[i] == 'D') y--;
        if (moves[i] == 'L') x++;
        if (moves[i] == 'R') x--;
    }
    return x == 0 && y == 0;
};

TypeScript

var judgeCircle = function (moves) {
  let x = 0
  let y = 0
  for (let i = 0; i < moves.length; i++) {
    switch (moves[i]) {
      case 'L': {
        x--
        break
      }
      case 'R': {
        x++
        break
      }
      case 'U': {
        y--
        break
      }
      case 'D': {
        y++
        break
      }
    }
  }
  return x === 0 && y === 0
};