This question is asked by Amazon. Given a string representing the sequence of moves a robot vacuum makes, return whether or not it will return to its original position. The string will only contain L, R, U, and D characters, representing left, right, up, and down respectively.

Example test-case:

"LR", return true
"URURD", return false
"RUULLDRD", return true

🗣️ Discussion:

Thinking about this problem for a few moments, we can realize this is a counting problem. For each move the vacuum makes, it must have a complement of that move to make sure it can return to its starting position. In this problem, L + R and U + D( meaning “undoes”). Once we see this intuition, it simply becomes a problem of checking if we have the same number of L and R characters and the same number of U and D characters. If we do, the vacuum has returned to its starting position. We can determine this by using two count variables LR and UD incrementing LR every time we see R and decrementing LR every time we see L(the same logic applies for incrementing UD when seeing U and D characters). If we reach the end of the vacuum’s moves and LR  and UD are both equal to zero we can return true and otherwise we can return false.

🎯 Solution

public bool vacuumReturnsToStart(string moves) {
    int UD = 0;
    int LR = 0;
    for(int i = 0; i < moves.Length; i++) {
        char current = moves[i];
        if(current == 'U') {
            UD++;
        } else if(current == 'D') {
            UD--;
        } else if(current == 'L') {
            LR++;
        } else if(current == 'R') {
            LR--;
        }
    }

    return UD == 0 && LR == 0;
}

Big-O Analysis

Runtime: O(N) where N is the number of moves the vacuum makesSpace complexity: O(1) or constant as we only need a few variables to solve the problem regardless of the number of moves the vacuum makes