algoadvance

Leetcode 657. Robot Return to Origin

Problem Statement

You are given a string moves that represents the movements of a robot on a 2D plane. The robot starts at the origin (0, 0) and each character in the string represents a move:

• ‘U’: move up one unit.
• ‘D’: move down one unit.
• ‘L’: move left one unit.
• ‘R’: move right one unit.

Determine if the robot returns to the origin after completing all of its moves. Return true if it returns to the origin, otherwise return false.

Clarifying Questions

1. What is the range of the length of the string moves?
   • The length of the string moves can range from 1 to 2 * 10^4.
2. Will the string moves contain only the characters ‘U’, ‘D’, ‘L’, ‘R’?
   • Yes, the string will only contain these characters.
3. Is there any consideration for case sensitivity in the input string?
   • The problem assumes that the input string will be in uppercase.

Strategy

1. Initialize Coordinates:
   • Start with two variables x and y initialized to 0, representing the current position of the robot.
2. Iterate through the Moves:
   • Loop through each character in the moves string and update the coordinates accordingly:
     • ‘U’ increments y by 1.
     • ‘D’ decrements y by 1.
     • ‘L’ decrements x by 1.
     • ‘R’ increments x by 1.
3. Check if at Origin:
   • After processing all moves, check if both x and y are 0. If they are, return true; otherwise, return false.

Code

public class Solution {
    public boolean judgeCircle(String moves) {
        int x = 0;
        int y = 0;

        for (char move : moves.toCharArray()) {
            switch (move) {
                case 'U':
                    y++;
                    break;
                case 'D':
                    y--;
                    break;
                case 'L':
                    x--;
                    break;
                case 'R':
                    x++;
                    break;
            }
        }

        return x == 0 && y == 0;
    }
}

Time Complexity

• Time Complexity: O(n), where n is the length of the input string moves. We only need to traverse the string once to determine the final position.
• Space Complexity: O(1), no additional space is needed that scales with input size, just a few integer variables.

With this approach, we efficiently determine if the robot returns to the origin after completing the series of moves.

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?