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^4moves only contains the characters 'U', 'D', 'L' and 'R'
Hints for Robot Return to Origin
Hint 1
Only the final position matters, not the path.
Hint 2
Track the horizontal and vertical offsets separately.
Hint 3
The robot is home exactly when the number of
Uequals the number ofDand the number ofLequals the number ofR.
How to solve Robot Return to Origin
The moves commute: the final position is (#R − #L, #U − #D), whatever the order.
Approach
- Keep
x = y = 0. - For each move, adjust
xforL/RandyforU/D. - Return whether
x == 0andy == 0.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Both coordinates must be zero — balancing only
U/Dis 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