Robot Return to Origin
EasyPrompt
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 * 104movesonly contains the characters'U','D','L'and'R'.
Approaches
2 approaches with complexity analysis and trade-offs.
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.
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.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Initialize two variables,
x = 0andy = 0, to track the robot's current position. - Iterate through each character
movein themovesstring. - Use a conditional (if-else or switch) to update
xandybased on themove:- 'U': Increment
y. - 'D': Decrement
y. - 'L': Decrement
x. - 'R': Increment
x.
- 'U': Increment
- After the loop, return the result of the boolean expression
x == 0 && y == 0.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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 ; } }/** * @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;};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 ; } };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 == 0Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.