Push Dominoes

Problem Statement

LeetCode-838: There are n dominoes in a line, and we place each domino vertically upright. In the beginning, we simultaneously push some of the dominoes either to the left or to the right.

After each second, each domino that is falling to the left pushes the adjacent domino on the left. Similarly, the dominoes falling to the right push their adjacent dominoes standing on the right.

When a vertical domino has dominoes falling on it from both sides, it stays still due to the balance of the forces.

For the purposes of this question, we will consider that a falling domino expends no additional force to a falling or already fallen domino.

You are given a string dominoes representing the initial state where:

dominoes[i] = 'L', if the ith domino has been pushed to the left,
dominoes[i] = 'R', if the ith domino has been pushed to the right, and
dominoes[i] = '.', if the ith domino has not been pushed.

Return a string representing the final state.

Approach

This problem is about simulating falling dominoes with specific rules:

• Dominoes can be in three states:
  • falling left (‘L’)
  • falling right (‘R’)
  • or standing (’.')
• A domino falling in one direction will push the adjacent domino in that direction
• When forces from both sides hit a domino, it remains standing
• Once a domino is falling or has fallen, it can’t be affected further

Based on the points mentioned above, we can see that for each standing domino, what determines whether it will fall left, right, or stay standing is the distance to the nearest falling domino in either direction.

• A standing domino (’.’) will fall right if there’s an ‘R’ pushing from the left with no opposing ‘L’
• It will fall left if there’s an ‘L’ pushing from the right with no opposing ‘R’
• If forces come from both sides, the domino’s fate depends on which force reaches it first (or if they reach simultaneously, it stays standing)

Algorithm

For each position with a standing domino, what if we calculate:

• The distance to the nearest ‘R’ on its left (if any)
• The distance to the nearest ‘L’ on its right (if any)

Then we can compare these distances to determine which force reaches it first. Let us try to explain this with the help of an example: R.....L

1. First, let us label each position with an index:

   Position: 0 1 2 3 4 5 6
   Domino:   R . . . . . L
   

2. For each standing domino (marked with ‘.’), we want to find:

   1. Distance to the nearest ‘R’ on its left
   2. Distance to the nearest ‘L’ on its right

Then for each ‘.’ position i, we compare $(i - left[i])$ with $(right[i] - i)$ to determine its final state.

Implementation

Here is a java implementation of the above approach:

public String pushDominoes(String dominoes) {
    int n = dominoes.length();

    int[] nearestROnLeft = new int[n];
    int[] nearestLOnRight = new int[n];

    char[] ch = dominoes.toCharArray();
    int pos = -1;

    // Find nearest 'R' on the left for each position
    for(int i=0; i < n; i++){
        if(ch[i] == 'R'){
            pos = i;
        }else if(ch[i] == 'L'){
            // If we encounter 'L', we need to reset the position
            pos = -1;
        }
        nearestROnLeft[i] = pos;
    }

    pos = -1;

    // Find nearest 'L' on the right for each position
    for(int i=n-1; i >= 0; i--){
        if(ch[i] == 'L'){
            pos = i;
        }else if(ch[i] == 'R'){
            // If we encounter 'R', we need to reset the position
            pos = -1;
        }
        nearestLOnRight[i] = pos;
    }

    // Now we can determine the final state of each domino
    for(int i=0; i < n; i++){
        // If the domino is standing ('.'), we need to check the distances
        if(ch[i] == '.'){
            // Calculate distances to nearest 'R' and 'L'
            // If there is no 'R' on the left, set distance to max value
            // If there is no 'L' on the right, set distance to max value
            int rDist = nearestROnLeft[i] == -1 ? Integer.MAX_VALUE : (i-nearestROnLeft[i]);
            int lDist = nearestLOnRight[i] == -1 ? Integer.MAX_VALUE : (nearestLOnRight[i] - i);

            // Compare distances to determine the final state
            // If the distance to 'R' is less than 'L', it will fall right
            // If the distance to 'L' is less than 'R', it will fall left
            // If they are equal, it will remain standing
            if(rDist < lDist){
                ch[i] = 'R';
            }else if(lDist < rDist){
                ch[i] = 'L';
            }
        }
    }
    return new String(ch);
}

Complexity Analysis

• Time Complexity: $O(n)$, where n is the length of the input string. We traverse the string a constant number of times.
• Space Complexity: $O(n)$, where n is the length of the input string. We use two arrays to store the nearest ‘R’ and ‘L’ positions.