Robot Return to Origin Interview Question for Amazon

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<sup>th</sup> 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^4
moves only contains the characters 'U', 'D', 'L' and 'R'.

The problem asks us to determine if a robot, starting at the origin (0, 0) of a 2D plane, returns to the origin after executing a sequence of moves. The moves are represented by a string, where 'U' denotes up, 'D' denotes down, 'L' denotes left, and 'R' denotes right. The robot's movement magnitude is the same for each move. We need to return true if the robot ends up at (0, 0), and false otherwise.

Here's how we can approach this problem:

Naive Solution: Iterate through the moves string. For each move, update the robot's position. If the move is 'U', increment the y-coordinate. If the move is 'D', decrement the y-coordinate. If the move is 'R', increment the x-coordinate. If the move is 'L', decrement the x-coordinate. After processing all moves, check if the robot's final position is (0, 0). This is a straightforward implementation.
Optimal Solution: The key idea here is that the number of 'U' moves must equal the number of 'D' moves, and the number of 'L' moves must equal the number of 'R' moves for the robot to return to the origin. We can count the occurrences of each move and compare 'U' with 'D' and 'L' with 'R'. If they are equal, the robot returns to the origin.

class Solution {
    /**
     * Determines if a robot returns to the origin after a series of moves.
     *
     * @param moves A string representing the sequence of moves (U, D, L, R).
     * @return True if the robot returns to the origin, false otherwise.
     */
    public boolean judgeCircle(String moves) {
        int x = 0;
        int y = 0;

        for (char move : moves.toCharArray()) {
            if (move == 'U') {
                y++;
            } else if (move == 'D') {
                y--;
            } else if (move == 'R') {
                x++;
            } else {
                x--;
            }
        }

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

class Solution {
    public boolean judgeCircle(String moves) {
        int uCount = 0;
        int dCount = 0;
        int lCount = 0;
        int rCount = 0;
        
        for (char c : moves.toCharArray()) {
            if (c == 'U') uCount++;
            else if (c == 'D') dCount++;
            else if (c == 'L') lCount++;
            else if (c == 'R') rCount++;
        }
        
        return uCount == dCount && lCount == rCount;
    }
}

Big(O) Run-time Analysis:

The optimal solution iterates through the moves string once. Therefore, the time complexity is O(n), where n is the length of the moves string.

Big(O) Space Usage Analysis:

The optimal solution uses a fixed number of variables (uCount, dCount, lCount, rCount) regardless of the input size. Thus, the space complexity is O(1), constant space.

Edge Cases:

Empty String: If the input string moves is empty, the robot is already at the origin, so we return true. The provided code handles this correctly, as the loop won't execute, and x and y will remain 0.
Null String: If the input string is null, it could throw a NullPointerException. It's good practice to add a null check at the beginning of the method: if (moves == null) return true; (or throw an IllegalArgumentException, depending on the requirements).
Invalid Characters: If the input string contains characters other than 'U', 'D', 'L', and 'R', the code will still execute, but the result might be incorrect. We could add a check for invalid characters and either ignore them or throw an exception.
Very Long String: For extremely long input strings, the integer counters could theoretically overflow, though this is unlikely in practice given the constraint 1 <= moves.length <= 2 * 10^4. If this were a concern, we could use long instead of int for the counters.

Here's the code that includes the null check to handle one of the edge cases:

class Solution {
    public boolean judgeCircle(String moves) {
        if (moves == null) return true; // Handle null input

        int uCount = 0;
        int dCount = 0;
        int lCount = 0;
        int rCount = 0;
        
        for (char c : moves.toCharArray()) {
            if (c == 'U') uCount++;
            else if (c == 'D') dCount++;
            else if (c == 'L') lCount++;
            else if (c == 'R') rCount++;
        }
        
        return uCount == dCount && lCount == rCount;
    }
}