Leetcode – Robot Return to Origin Solution in Python

Spread the love

Introduction

In the field of robotics and automation, programming robots to perform tasks and analyze their paths is a common challenge. The “Robot Return to Origin” problem on Leetcode is a simplified representation of such challenges. It tests the ability of a programmer to work with strings and implement basic logic to analyze movements. In this article, we will dive deep into the problem statement, discuss different algorithms to solve the problem, and provide Python code for each of these solutions.

Problem Statement

There is a robot starting at the position (0, 0), the origin, on a 2D plane. The robot can receive one of four instructions:

  • “U”, which means move up one unit,
  • “D”, which means move down one unit,
  • “L”, which means move left one unit,
  • “R”, which means move right one unit.

The robot moves according to a given string of instructions. The task is to return true if the robot returns to its starting point (origin), and false if it does not.

Example:

Input: moves = "UD"

Output: true

Explanation: The robot moves up one unit with “U”, and then down one unit with “D”, returning it to (0, 0).

Note:

  • The string moves will have length at most 10,000.
  • moves will only consist of characters ‘U’, ‘D’, ‘L’ and ‘R’.

Solution

1. Counting Movements

A straightforward approach to solving this problem is to count the number of times the robot moves in each direction. For the robot to return to the origin, the number of moves up must equal the number of moves down, and the number of moves left must equal the number of moves right.

  1. Initialize counters for up, down, left, and right movements.
  2. Iterate through each character in the moves string.
  3. For each character, increment the appropriate counter.
  4. Check if the number of up movements equals the number of down movements, and the number of left movements equals the number of right movements.
def robot_return_to_origin(moves):
    up = down = left = right = 0
    
    for move in moves:
        if move == 'U':
            up += 1
        elif move == 'D':
            down += 1
        elif move == 'L':
            left += 1
        elif move == 'R':
            right += 1
    
    return up == down and left == right

Time Complexity:

  • O(n), where n is the length of the moves string.

Space Complexity:

  • O(1), as we are using a constant amount of space.

2. Using Python’s Collection

We can optimize the code for readability and conciseness using Python’s collections module. We can use a Counter to count the occurrences of each movement and then simply compare the counts.

  1. Use a Counter to count the occurrences of each movement in the moves string.
  2. Check if the count of up movements equals the count of down movements, and the count of left movements equals the count of right movements.
from collections import Counter

def robot_return_to_origin(moves):
    counts = Counter(moves)
    return counts['U'] == counts['D'] and counts['L'] == counts['R']

Time Complexity:

  • O(n), where n is the length of the moves string.

Space Complexity:

  • O(1), as the Counter uses a constant amount of space for the 4 possible movements.

Conclusion

In this article, we explored the “Robot Return to Origin” problem on Leetcode and discussed two different approaches in Python: Counting Movements and Using Python’s Collection. Both solutions are efficient and use constant space.

Leave a Reply