# Robot Return to Origin
**Difficulty:** EASY
[External](https://leetcode.com/problems/robot-return-to-origin)
Canonical: https://scaleengineer.com/dsa/problems/robot-return-to-origin
**Data structures:** String
**Companies:** [Yandex](https://scaleengineer.com/companies/yandex)
---
## Problem
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 `moves[i]` represents its `ith` move. Valid moves are `'R'` (right), `'L'` (left), `'U'` (up), and `'D'` (down).

Return `true` _if the robot returns to the origin after it finishes all of its moves, or_ `false` _otherwise_.

**Note**: The way that the robot is "facing" is irrelevant. `'R'` will always make the robot move to the right once, `'L'` will always make it move left, etc. Also, assume that the magnitude of the robot's movement is the same for each move.

**Example 1:**

**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.

**Example 2:**

**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 * 104`
* `moves` only contains the characters `'U'`, `'D'`, `'L'` and `'R'`.

# Approaches
## Simulation with Path Tracking
This approach simulates the robot's movement step-by-step and stores every position it visits. By tracking the entire path, we can determine the final position. This is a straightforward but less efficient way to solve the problem due to its space usage.
**Time:** O(N), where N is the length of the `moves` string. We iterate through the string once. · **Space:** O(N), where N is the length of the `moves` string. We need to store N+1 coordinate points in the list.
**Pros:** Simple to understand and implement.; Provides the full path of the robot, which could be useful for variations of the problem.
**Cons:** Uses unnecessary space. The problem only asks for the final position, not the entire path.; For a large number of moves, this can lead to high memory consumption and potential performance issues.
### Explanation
In this method, we maintain a list of coordinates representing the robot's path. We start by adding the origin `(0, 0)` to our list.

Then, we loop through the `moves` string. For each character representing a move, we look at the last position stored in our list, calculate the next position, and add this new position to the end of the list. For example, if the last position was `(x, y)` and the move is 'U', the new position will be `(x, y+1)`.

After iterating through all the moves, the last element in our list will be the robot's final position. We then simply check if this final position is `(0, 0)`. If it is, we return `true`; otherwise, we return `false`.

While this correctly solves the problem, it's inefficient because it stores a lot of information (the entire path) that isn't required by the problem statement.

```java
import java.awt.Point;
import java.util.ArrayList;
import java.util.List;

class Solution {
    public boolean judgeCircle(String moves) {
        List<Point> path = new ArrayList<>();
        path.add(new Point(0, 0));

        for (char move : moves.toCharArray()) {
            Point lastPosition = path.get(path.size() - 1);
            int newX = lastPosition.x;
            int newY = lastPosition.y;

            if (move == 'U') {
                newY++;
            } else if (move == 'D') {
                newY--;
            } else if (move == 'L') {
                newX--;
            } else if (move == 'R') {
                newX++;
            }
            path.add(new Point(newX, newY));
        }

        Point finalPosition = path.get(path.size() - 1);
        return finalPosition.x == 0 && finalPosition.y == 0;
    }
}
```
### Algorithm
- Initialize a list to store the coordinates of the robot's path, starting with the origin `(0, 0)`.
- Iterate through each move in the input string.
- For each move, calculate the new coordinates based on the last recorded position.
- The new coordinates are then added to the path list.
- After processing all the moves, check the final coordinates in the list. If the final position is `(0, 0)`, the robot has returned to the origin.

## Optimized Simulation with Constant Space
A more efficient approach is to track only the current position of the robot without storing its entire path. The robot returns to the origin if and only if its net displacement along both the horizontal and vertical axes is zero. This can be achieved by using two variables to keep track of the x and y coordinates.
**Time:** O(N), where N is the length of the `moves` string. We perform a single pass over the string. · **Space:** O(1). We only use a fixed number of variables (`x` and `y`) regardless of the input size.
**Pros:** Highly efficient in both time and space.; Optimal solution for this problem.; Simple and easy to implement.
**Cons:** This approach does not retain the path information, which might be a limitation if the problem requirements were different.
### Explanation
Instead of storing every position, we only need to know the final position. We can simulate the robot's movement by maintaining its current coordinates. We initialize two variables, `x` and `y`, to `0`.

We then iterate through the `moves` string. For each character, we update the coordinates:
- 'U' moves the robot up, so we increment `y`.
- 'D' moves the robot down, so we decrement `y`.
- 'R' moves the robot right, so we increment `x`.
- 'L' moves the robot left, so we decrement `x`.

After processing all the moves, the variables `x` and `y` will hold the final coordinates. The robot is back at the origin if and only if `x` is `0` and `y` is `0`. This is equivalent to checking if the number of 'U' moves equals the number of 'D' moves, and the number of 'L' moves equals the number of 'R' moves. This approach is optimal as it processes the input in a single pass with constant extra memory.

```java
class Solution {
    public boolean judgeCircle(String moves) {
        int x = 0;
        int y = 0;
        for (char move : moves.toCharArray()) {
            switch (move) {
                case 'U': y++; break;
                case 'D': y--; break;
                case 'L': x--; break;
                case 'R': x++; break;
            }
        }
        return x == 0 && y == 0;
    }
}
```
### Algorithm
- Initialize two variables, `x = 0` and `y = 0`, to track the robot's current position.
- Iterate through each character `move` in the `moves` string.
- Use a conditional (if-else or switch) to update `x` and `y` based on the `move`:
  - 'U': Increment `y`.
  - 'D': Decrement `y`.
  - 'L': Decrement `x`.
  - 'R': Increment `x`.
- After the loop, return the result of the boolean expression `x == 0 && y == 0`.

# Solutions
### Java

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

### JavaScript

```javascript
/** * @param {string} moves * @return {boolean} */ var judgeCircle = function (
  moves,
) {
  let [x, y] = [0, 0];
  for (const c of moves) {
    if (c === " U ") {
      y++;
    } else if (c === " D ") {
      y--;
    } else if (c === " L ") {
      x--;
    } else {
      x++;
    }
  }
  return x === 0 && y === 0;
};

```

### CPP

```cpp
class Solution { public: bool judgeCircle ( string moves ) { int x = 0 , y = 0 ; for ( char c : moves ) { switch ( c ) { case 'U' : y ++ ; break ; case 'D' : y -- ; break ; case 'L' : x -- ; break ; case 'R' : x ++ ; break ; } } return x == 0 && y == 0 ; } };
```

### Python

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