657. Robot Return to Origin

EasyStringSimulation
Leetcode Link

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:

How many ways can you arrange the three letters A, B and C?

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:

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

  2. Loop through each character in the moves string. This string is the sequence of moves the robot is to perform.

  3. 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.
  4. After the loop completes, all the moves have been simulated, and the robot's final position has been updated accordingly.

  5. 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's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

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.

  1. 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).

  2. We start looping through the moves string.

  3. 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)
  4. 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.
  5. The third character is 'L'. The robot moves left, resulting in the decrement of x.

    • New position: (x, y) = (-1, 0)
  6. The last character is 'R'. This is a move to the right, which means we increment x.

    • Final position: (x, y) = (0, 0)
  7. We have completed the loop and processed all the moves. The robot's final position is at the origin, where it started.

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

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

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

Python Solution

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

Java Solution

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

C++ Solution

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

Typescript Solution

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
Fast Track Your Learning with Our Quick Skills Quiz:

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

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.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫