657. Robot Return to Origin

EasyStringSimulation

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

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 and y, both set to 0. 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.
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 and y are 0. If they are, it means the robot returned to the origin after all its moves. Therefore, return true. If either x or y is not 0, return false.

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What are the most two important steps in writing a depth first search function? (Select 2)

Determine state to pass down to recursive function callDetermine return valueDetermine how many recursive calls will be madeTracing the recursive calls

Example 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 and y, to 0. 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 increment y.
- New position: (x, y) = (0, 1)
The next character is 'D'. This move is down, so we decrement y.
- New position: (x, y) = (0, 0). The robot has returned to the origin, but we continue to process all moves.
The third character is 'L'. The robot moves left, resulting in the decrement of x.
- New position: (x, y) = (-1, 0)
The last character is 'R'. This is a move to the right, which means we increment x.
- Final position: (x, y) = (0, 0)
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 and y are 0, our algorithm returns true. 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

Not Sure What to Study? Take the 2-min Quiz：

Which algorithm should you use to find a node that is close to the root of the tree?

Depth First SearchBreadth First Search

I don’t know

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.

Fast Track Your Learning with Our Quick Skills Quiz:

How does quick sort divide the problem into subproblems?

Divide the array into two equal halves by indexDivide the array into two based on whether an element is smaller than an arbitrary valueDivide the array into a stray element and the rest of the arrayQuick sort does not use divide and conquer

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

657. Robot Return to Origin

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Recommended Readings