algoadvance

Leetcode 657. Robot Return to Origin

Problem Statement

The problem is taken from LeetCode:

There is a robot starting at position (0, 0), the origin, on a 2D plane. Given a sequence of its moves represented by a string, return true if the robot returns to the origin after completing all of its moves, or false otherwise.

The input string moves contains characters that represent the robot’s movement:

• 'U' (Up)
• 'D' (Down)
• 'R' (Right)
• 'L' (Left)

The robot makes one move per character in the string.

Clarifying Questions

1. Input Length Constraints?
   • The length of the input string moves can range from 1 to 10,000.
2. Input Validity?
   • It is guaranteed that the input string only contains characters 'U', 'D', 'L', and 'R'.

Strategy

To determine if the robot ends up at the origin (0, 0) after executing all moves, consider the net effect of each type of move:

• Each 'U' (Up) increases the y-coordinate by 1.
• Each 'D' (Down) decreases the y-coordinate by 1.
• Each 'R' (Right) increases the x-coordinate by 1.
• Each 'L' (Left) decreases the x-coordinate by 1.

To solve the problem:

1. Initialize coordinates (x, y) to (0, 0).
2. Iterate through the moves string and adjust the coordinates based on the type of move.
3. After processing all moves, check if (x, y) is (0, 0).

If (x, y) is (0, 0), return true. Otherwise, return false.

Time Complexity

• The time complexity is (O(n)), where (n) is the length of the moves string, as we iterate through the string once.
• The space complexity is (O(1)) since we use only a fixed amount of additional space regardless of the input size.

Code

Here is the C++ implementation of the solution:

#include <string>

using namespace std;

class Solution {
public:
    bool judgeCircle(string moves) {
        int x = 0, y = 0;
        
        for (char move : moves) {
            if (move == 'U') {
                y++;
            } else if (move == 'D') {
                y--;
            } else if (move == 'R') {
                x++;
            } else if (move == 'L') {
                x--;
            }
        }
        
        return (x == 0) && (y == 0);
    }
};

This code solves the problem by simply iterating through the moves string, updating the x and y coordinates, and finally checking if the coordinates return to the origin.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?