Robot Return to Origin

Easy

Asked by:

67 views

Topics:

Strings

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 i^th 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 * 10⁴
moves only contains the characters 'U', 'D', 'L' and 'R'.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

The input string 'moves' contains a sequence of moves. What characters can appear in the string, and are they case-sensitive?
Is the input string 'moves' guaranteed to only contain valid move characters, or should I handle invalid input?
If the robot returns to the origin, should I return true or a coordinate representing the origin (0, 0)?
Can the input string 'moves' be empty or null? If so, what should I return?
Is there a maximum length for the input string 'moves'?

Brute Force Solution

Approach

Imagine the robot starts at a point (0,0). The brute force approach simulates every single move the robot makes, one at a time, following the given sequence of instructions. We meticulously track the robot's position after each move and finally check if it returns to the origin.

Here's how the algorithm would work step-by-step:

Begin at the starting point, which is the origin.
Look at the very first move in the instruction sequence.
Update the robot's position based on that first move. For example, if it says 'up', move the robot up one unit.
Now, look at the second move in the sequence and update the robot's position again.
Continue this process, updating the robot's position after each move in the sequence, one by one.
Once you've processed all the moves in the sequence, check the robot's final position.
If the final position is the same as the starting position (the origin), then the robot returned to the origin. Otherwise, it didn't.

Code Implementation

def robot_return_to_origin_brute_force(moves):
    horizontal_position = 0
    vertical_position = 0

    # Iterate through each move in the sequence
    for move in moves:
        # Update the robot's position based on the move
        if move == 'U':
            vertical_position += 1
        elif move == 'D':
            vertical_position -= 1
        elif move == 'L':
            horizontal_position -= 1
        elif move == 'R':
            horizontal_position += 1

    # Check if the robot returned to the origin
    # Necessary to determine if net displacement is zero
    if horizontal_position == 0 and vertical_position == 0:
        return True
    else:
        return False

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string 'moves' of length n, representing the sequence of robot movements. For each move, it updates the robot's x and y coordinates based on the direction. This update operation takes constant time O(1). Since the algorithm performs a constant time operation for each of the n moves, the overall time complexity is directly proportional to the number of moves, resulting in O(n).

Space Complexity

O(1) – The provided solution tracks the robot's position using two variables to represent the x and y coordinates. These variables are updated after each move, but their number remains constant regardless of the number of moves (N) in the input sequence. No additional data structures that scale with the input size are used. Thus, the space complexity is constant.

Optimal Solution

Approach

The goal is to determine if a robot, given a series of movements, ends up back at its starting point. The efficient approach avoids tracking the robot's path and instead focuses on counting movements in opposite directions to see if they cancel each other out.

Here's how the algorithm would work step-by-step:

Imagine the robot starts at (0, 0) on a map.
Keep track of the total number of 'up' and 'down' moves.
Also, keep track of the total number of 'left' and 'right' moves.
If the number of 'up' moves equals the number of 'down' moves, then the robot hasn't moved vertically.
Similarly, if the number of 'left' moves equals the number of 'right' moves, then the robot hasn't moved horizontally.
If both conditions are true (vertical movement is zero and horizontal movement is zero), the robot returned to its origin.

Code Implementation

def robot_return_to_origin(moves): 
    up_down_count = 0
    left_right_count = 0

    for move in moves:
        if move == 'U':
            up_down_count += 1
        elif move == 'D':
            up_down_count -= 1
        elif move == 'L':
            left_right_count += 1
        else:
            left_right_count -= 1

    #If vertical displacement is zero
    if up_down_count == 0:

        # If horizontal displacement is zero
        if left_right_count == 0:
            return True
        else:
            return False
    else:
        return False

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string 'moves' once. Each character in the string is examined to increment a counter for 'up', 'down', 'left', or 'right' movements. The number of operations is directly proportional to the length 'n' of the 'moves' string, as each character is processed only once. Therefore, the time complexity is O(n).

Space Complexity

O(1) – The algorithm uses a fixed number of integer variables to count the number of 'up', 'down', 'left', and 'right' moves. The space required for these counters does not depend on the length of the input string of moves, which we can denote as N. Therefore, the auxiliary space used is constant, regardless of the input size.

Edge Cases

Case	How to Handle
Null or empty input string	Return true immediately as an empty path means the robot is at the origin.
Input string with invalid characters (not 'U', 'D', 'L', 'R')	Ignore invalid characters and process only valid moves, or throw an exception if strict validation is required.
Input string with a very large number of moves	The solution should scale linearly with the input string length, which is acceptable; watch for potential memory issues with extremely long strings.
Input string with an odd number of moves	The robot cannot return to origin with an odd number of moves if each move has an opposite counterpart.
Input string with only 'U' moves	The robot will never return to the origin; the final coordinates will be (0, string.length).
Integer overflow for x or y coordinates after many moves	Using 'int' for coordinates is generally sufficient, but for extremely long paths, consider using 'long' or checking for overflow.
Input string with Unicode characters outside of ASCII range	Ensure the code correctly handles Unicode input if the problem statement allows Unicode characters, by correctly interpreting unicode strings.
The same number of horizontal (L/R) and vertical (U/D) moves but not in cancelling sequence	The robot will return to the origin as long as the number of 'U' equals 'D' and the number of 'L' equals 'R'.

Null or empty input string

How to Handle:

Return true immediately as an empty path means the robot is at the origin.

Input string with invalid characters (not 'U', 'D', 'L', 'R')

How to Handle:

Ignore invalid characters and process only valid moves, or throw an exception if strict validation is required.

Input string with a very large number of moves

How to Handle:

The solution should scale linearly with the input string length, which is acceptable; watch for potential memory issues with extremely long strings.

Input string with an odd number of moves

How to Handle:

The robot cannot return to origin with an odd number of moves if each move has an opposite counterpart.

Input string with only 'U' moves

How to Handle:

The robot will never return to the origin; the final coordinates will be (0, string.length).

Integer overflow for x or y coordinates after many moves

How to Handle:

Using 'int' for coordinates is generally sufficient, but for extremely long paths, consider using 'long' or checking for overflow.

Input string with Unicode characters outside of ASCII range

How to Handle:

Ensure the code correctly handles Unicode input if the problem statement allows Unicode characters, by correctly interpreting unicode strings.

The same number of horizontal (L/R) and vertical (U/D) moves but not in cancelling sequence

How to Handle:

The robot will return to the origin as long as the number of 'U' equals 'D' and the number of 'L' equals 'R'.