657. Robot Return to Origin
Problem Description
This LeetCode problem involves determining whether a robot, which starts at the origin (0, 0) on a 2D plane, returns to its starting point after executing a series of moves. The series of moves is given as a string where each character corresponds to a move in one of four possible directions: 'R' (right), 'L' (left), 'U' (up), and 'D' (down). The task is to analyze this string and return true
if the robot ends up at the origin after all the moves or false
otherwise. The key point is to keep track of the robot's position relative to the origin, regardless of how it's facing, and verify if it returns to (0, 0).
Intuition
The solution is based on the simple idea of simulating the robot's moves by keeping track of its position on the 2D plane with a pair of variables, one for the horizontal axis (x) and the other for the vertical axis (y). Initially, the robot is at (0, 0). For each move, depending on the direction, we increment or decrement the corresponding axis value - 'R' increases x, 'L' decreases x, 'U' increases y, and 'D' decreases y. After processing all moves, if the robot's position is still (0, 0), it means the robot has returned to the starting point, and we return true
; otherwise, false
.
This approach relies on the observation that for the robot to return to the origin, it must have performed equal numbers of 'L' and 'R' moves as well as equal numbers of 'U' and 'D' moves. This pair of equalities ensures that the robot has undone all horizontal and vertical displacements, respectively.
Solution Approach
The implementation of the solution uses a straightforward, iterative approach to simulate the moves of the robot. Here is a step-by-step explanation of the algorithm and the data structures used:
-
Initialize two variables,
x
andy
, both set to0
. These variables represent the position of the robot on the x-axis (horizontal) and y-axis (vertical) respectively. -
Loop through each character in the
moves
string. This string is the sequence of moves the robot is to perform. -
For each character (representing a move), compare it to the possible moves 'R', 'L', 'U', 'D':
- If the move is 'R' (right), increment the
x
variable to simulate a move to the right. - If the move is 'L' (left), decrement the
x
variable to simulate a move to the left. - If the move is 'U' (up), increment the
y
variable to simulate a move upward. - If the move is 'D' (down), decrement the
y
variable to simulate a move downward.
- If the move is 'R' (right), increment the
-
After the loop completes, all the moves have been simulated, and the robot's final position has been updated accordingly.
-
Finally, check if both
x
andy
are0
. If they are, it means the robot returned to the origin after all its moves. Therefore, returntrue
. If eitherx
ory
is not0
, returnfalse
.
The algorithm uses constant extra space, only needing two integer variables, regardless of the length of the moves
string. The time complexity is linear with respect to the length of the moves
string since it has to check each move exactly once.
No additional data structures or complex patterns are needed. The solution is optimal in terms of both time and space complexity, which are O(n) and O(1), respectively, with n
being the length of the moves string.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider an example where the moves string given is "UDLR"
. According to the problem description, we need to simulate these moves and determine if the robot returns to the origin (0, 0)
afterwards.
-
We initialize two variables,
x
andy
, to0
. These represent the robot's current position on the x and y axes, respectively:(x, y) = (0, 0)
. -
We start looping through the
moves
string. -
The first character is
'U'
. This indicates a move up. According to our algorithm, this means we incrementy
.- New position:
(x, y) = (0, 1)
- New position:
-
The next character is
'D'
. This move is down, so we decrementy
.- New position:
(x, y) = (0, 0)
. The robot has returned to the origin, but we continue to process all moves.
- New position:
-
The third character is
'L'
. The robot moves left, resulting in the decrement ofx
.- New position:
(x, y) = (-1, 0)
- New position:
-
The last character is
'R'
. This is a move to the right, which means we incrementx
.- Final position:
(x, y) = (0, 0)
- Final position:
-
We have completed the loop and processed all the moves. The robot's final position is at the origin, where it started.
-
Since both
x
andy
are0
, our algorithm returnstrue
. This indicates that the robot indeed returned to its starting point after executing the given series of moves.
In this walk-through, we can see how the algorithm effectively uses the position variables to keep track of the robot's location. It's clear that for every move away from the origin, there is a counter move that brings the robot back to the origin, thus restoring both x
and y
to 0
.
Solution Implementation
1class Solution:
2 def judgeCircle(self, moves: str) -> bool:
3 # Initialize coordinates at the origin point (0,0)
4 horizontal_position = 0
5 vertical_position = 0
6
7 # Iterate through each move in the string
8 for move in moves:
9 # Move right: increase horizontal position
10 if move == 'R':
11 horizontal_position += 1
12 # Move left: decrease horizontal position
13 elif move == 'L':
14 horizontal_position -= 1
15 # Move up: increase vertical position
16 elif move == 'U':
17 vertical_position += 1
18 # Move down: decrease vertical position
19 elif move == 'D':
20 vertical_position -= 1
21
22 # If both positions are back to 0, return True (circle complete)
23 return horizontal_position == 0 and vertical_position == 0
24
25# The function 'judgeCircle' analyzes a sequence of moves (R, L, U, D)
26# and determines if they form a circle leading back to the origin (0,0).
27
1class Solution {
2 // Method to judge whether the robot returns to the origin after executing a sequence of moves
3 public boolean judgeCircle(String moves) {
4 // Initial position of the robot
5 int x = 0; // Horizontal axis displacement
6 int y = 0; // Vertical axis displacement
7
8 // Loop through the moves string to process each move
9 for (int i = 0; i < moves.length(); ++i) {
10 // Get the current move
11 char move = moves.charAt(i);
12
13 // Process the move to calculate the displacement
14 if (move == 'R') { // Right move: increase x-coordinate
15 x++;
16 } else if (move == 'L') { // Left move: decrease x-coordinate
17 x--;
18 } else if (move == 'U') { // Up move: increase y-coordinate
19 y++;
20 } else if (move == 'D') { // Down move: decrease y-coordinate
21 y--;
22 }
23 // Note: No 'else' case since we assume all characters in 'moves' are valid (only 'R', 'L', 'U', 'D')
24 }
25
26 // Check if the robot returned to the origin (0,0)
27 return x == 0 && y == 0;
28 }
29}
30
1#include <string>
2#include <unordered_map>
3
4// Function to determine if a series of moves for a robot
5// in a plane starting at the origin (0,0) will result in the robot
6// returning to the original position
7bool judgeCircle(std::string moves) {
8 // Variables to hold the robot's x and y coordinates,
9 // initialized to the start position (0, 0)
10 int xCoordinate = 0;
11 int yCoordinate = 0;
12
13 // Creating a map for defining the movements associated
14 // with each possible direction
15 const std::unordered_map<char, std::pair<int, int>> directions {
16 {'R', {1, 0}}, // Right move increases x coordinate by 1
17 {'L', {-1, 0}}, // Left move decreases x coordinate by 1
18 {'U', {0, 1}}, // Up move increases y coordinate by 1
19 {'D', {0, -1}} // Down move decreases y coordinate by 1
20 };
21
22 // Iterate over each move in the string
23 for (char move : moves) {
24 // Look up the movement associated with the direction
25 const auto& delta = directions.at(move);
26 // Update the robot's position coordinates
27 xCoordinate += delta.first;
28 yCoordinate += delta.second;
29 }
30
31 // Check if the robot is back at the origin (0,0)
32 // If so, return true, otherwise return false
33 return xCoordinate == 0 && yCoordinate == 0;
34}
35
1// TypeScript function to determine if a series of moves for a robot
2// in a plane starting at the origin (0,0) will result in the robot
3// returning to the original position
4function judgeCircle(moves: string): boolean {
5 // Variables to hold the robot's position coordinates,
6 // initialized to the start position (0,0)
7 let xCoordinate = 0,
8 yCoordinate = 0;
9
10 // Object representing the possible directions and their respective movements
11 const directions = {
12 'R': [1, 0], // Right move (x coordinate +1)
13 'L': [-1, 0], // Left move (x coordinate -1)
14 'U': [0, 1], // Up move (y coordinate +1)
15 'D': [0, -1], // Down move (y coordinate -1)
16 };
17
18 // Iterate over each move in the input string
19 for (let move of moves) {
20 // Get the directional movements for the current move
21 const [deltaX, deltaY] = directions[move];
22 // Update the robot's position coordinates
23 xCoordinate += deltaX;
24 yCoordinate += deltaY;
25 }
26
27 // Return true if the robot is back at the origin (0,0), false otherwise
28 return xCoordinate === 0 && yCoordinate === 0;
29}
30
Time and Space Complexity
The time complexity of the given code can be analyzed as follows: The function judgeCircle
iterates through each character in the input string moves
. The number of operations per character is constant (either increment or decrement operations). Therefore, the time complexity is directly proportional to the length of moves
, which gives us a time complexity of O(n)
, where n
is the number of moves.
The space complexity of the code is also easy to determine: the only extra space used are the two integer variables x
and y
, which store the coordinates. These variables use a constant amount of space regardless of the input size, thus the space complexity is O(1)
, denoting constant space usage.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!