#838 Push Dominoes - Solution

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 i^th domino has been pushed to the left,
dominoes[i] = 'R', if the i^th domino has been pushed to the right, and
dominoes[i] = '.', if the i^th domino has not been pushed.

Return a string representing the final state.

Example 1:

Input: dominoes = "RR.L"
Output: "RR.L"
Explanation: The first domino expends no additional force on the second domino.

Example 2:

Input: dominoes = ".L.R...LR..L.."
Output: "LL.RR.LLRRLL.."

Constraints:

n == dominoes.length
1 <= n <= 10⁵
dominoes[i] is either 'L', 'R', or '.'.

The key idea in #838 Push Dominoes is to simulate how forces propagate across the domino line. Each domino can be influenced by a push from the left (L) or the right (R). A common strategy is to analyze the segments between non-dot characters and determine how the dominoes in between should fall.

One effective method uses a two-pointer technique. Traverse the string while tracking the last seen force and the next force. If the pattern is L...L or R...R, all dominoes in between fall in the same direction. If it is R...L, dominoes fall inward from both sides. For L...R, the middle dominoes remain upright because the forces move away from each other.

Another perspective treats the pushes as force propagation, computing influence from left-to-right and right-to-left and combining them to determine the final state. Both approaches run in linear time since each domino is processed a constant number of times.

Overall, the optimal solution achieves O(n) time complexity with O(n) or O(1) extra space depending on the implementation.

Approach	Time Complexity	Space Complexity
Two-Pointer Segment Analysis	O(n)	O(1)
Force Propagation (Left & Right Influence Arrays)	O(n)	O(n)

Solutions (6)

Approach 1: Two Pass Force Calculation

In this approach, we simulate the forces acting on the dominoes as a one-dimensional array of forces. Initially, each domino has zero force. We perform two passes: from left to right, and then from right to left. In the first pass, we apply forces caused by 'R' and increase the force gradually by 1 for each subsequent domino. In the second pass, we apply forces caused by 'L' and decrease the force by 1 for each subsequent domino. Finally, the resultant force at each position determines whether the domino remains upright (force=0), falls to the right (force>0), or falls to the left (force<0).

Time complexity: O(n), where n is the number of dominoes since we traverse the dominoes twice.
Space complexity: O(n) due to the 'forces' array.

Python C JavaScript

1function pushDominoes(dominoes) {
2    const n = dominoes.length;
3    const forces = Array(n).fill(0);
4
5    // Calculate right forces
6    let force = 0;
7    for (let i = 0; i < n; i++) {
8        if (dominoes[i] === 'R') {
9            force = n;
10        } else if (dominoes[i] === 'L') {
11            force = 0;
12        } else {
13            force = Math.max(force - 1, 0);
14        }
15        forces[i] = force;
16    }
17
18    // Calculate left forces
19    force = 0;
20    for (let i = n - 1; i >= 0; i--) {
21        if (dominoes[i] === 'L') {
22            force = n;
23        } else if (dominoes[i] === 'R') {
24            force = 0;
25        } else {
26            force = Math.max(force - 1, 0);
27        }
28        forces[i] -= force;
29    }
30
31    // Determine the final state
32    return forces.map(f => f === 0 ? '.' : (f > 0 ? 'R' : 'L')).join('');
33}

Explanation

In this JavaScript code, the same two-pass technique is applied to determine the resultant forces on the dominoes. This appends the final states into an array that converts to a string to output.

Approach 2: Simulate using Queue

This approach is also efficient and leverages a queue to process and simulate the domino effect until stability. We maintain a queue that handles dominos that need to be processed next, checking to apply the effect of the nearest 'L' or 'R'. This is somewhat similar to breadth-first search (BFS) in tree/graph traversal.

Time complexity: O(n), since each domino movement is processed exactly once.
Space complexity: O(n), due to the queue storing no more than all domino positions.

Java C++C#

1#include <queue>
2#include <string>
3
4class Solution {
public:
    std::string pushDominoes(std::string dominoes) {
        int n = dominoes.size();
        std::string result = dominoes;
        std::queue<int> queue;

        for (int i = 0; i < n; ++i) {
            if (dominoes[i] != '.') {
                queue.push(i);
            }
        }

        while (!queue.empty()) {
            int i = queue.front(); queue.pop();
            char d = result[i];

            if (d == 'L' && i > 0 && result[i - 1] == '.') {
                result[i - 1] = 'L';
                queue.push(i - 1);
            }
            if (d == 'R' && i + 1 < n && result[i + 1] == '.') {
                if (i + 2 < n && result[i + 2] == 'L') {
                    continue;
                }
                result[i + 1] = 'R';
                queue.push(i + 1);
            }
        }

        return result;
    }
};