Code Implementation

class Solution:
    def pushDominoes(self, dominoes: str) -> str:
        n = len(dominoes)
        forces = [0] * n

        # Left to right
        force = 0
        for i in range(n):
            if dominoes[i] == 'R':
                force = n
            elif dominoes[i] == 'L':
                force = 0
            else:
                force = max(force - 1, 0)
            forces[i] += force

        # Right to left
        force = 0
        for i in range(n - 1, -1, -1):
            if dominoes[i] == 'L':
                force = n
            elif dominoes[i] == 'R':
                force = 0
            else:
                force = max(force - 1, 0)
            forces[i] -= force

        result = []
        for f in forces:
            if f > 0:
                result.append('R')
            elif f < 0:
                result.append('L')
            else:
                result.append('.')
        return ''.join(result)
      

class Solution {
public:
    string pushDominoes(string dominoes) {
        int n = dominoes.size();
        vector forces(n, 0);

        int force = 0;
        // Left to right
        for (int i = 0; i < n; ++i) {
            if (dominoes[i] == 'R') {
                force = n;
            } else if (dominoes[i] == 'L') {
                force = 0;
            } else {
                force = max(force - 1, 0);
            }
            forces[i] += force;
        }

        force = 0;
        // Right to left
        for (int i = n - 1; i >= 0; --i) {
            if (dominoes[i] == 'L') {
                force = n;
            } else if (dominoes[i] == 'R') {
                force = 0;
            } else {
                force = max(force - 1, 0);
            }
            forces[i] -= force;
        }

        string result;
        for (int f : forces) {
            if (f > 0) result += 'R';
            else if (f < 0) result += 'L';
            else result += '.';
        }
        return result;
    }
};
      

class Solution {
    public String pushDominoes(String dominoes) {
        int n = dominoes.length();
        int[] forces = new int[n];

        int force = 0;
        // Left to right
        for (int i = 0; i < n; i++) {
            if (dominoes.charAt(i) == 'R') {
                force = n;
            } else if (dominoes.charAt(i) == 'L') {
                force = 0;
            } else {
                force = Math.max(force - 1, 0);
            }
            forces[i] += force;
        }

        force = 0;
        // Right to left
        for (int i = n - 1; i >= 0; i--) {
            if (dominoes.charAt(i) == 'L') {
                force = n;
            } else if (dominoes.charAt(i) == 'R') {
                force = 0;
            } else {
                force = Math.max(force - 1, 0);
            }
            forces[i] -= force;
        }

        StringBuilder result = new StringBuilder();
        for (int f : forces) {
            if (f > 0) result.append('R');
            else if (f < 0) result.append('L');
            else result.append('.');
        }
        return result.toString();
    }
}
      

var pushDominoes = function(dominoes) {
    const n = dominoes.length;
    const forces = new Array(n).fill(0);

    let force = 0;
    // Left to right
    for (let i = 0; i < n; i++) {
        if (dominoes[i] === 'R') {
            force = n;
        } else if (dominoes[i] === 'L') {
            force = 0;
        } else {
            force = Math.max(force - 1, 0);
        }
        forces[i] += force;
    }

    force = 0;
    // Right to left
    for (let i = n - 1; i >= 0; i--) {
        if (dominoes[i] === 'L') {
            force = n;
        } else if (dominoes[i] === 'R') {
            force = 0;
        } else {
            force = Math.max(force - 1, 0);
        }
        forces[i] -= force;
    }

    let result = '';
    for (let f of forces) {
        if (f > 0) result += 'R';
        else if (f < 0) result += 'L';
        else result += '.';
    }
    return result;
};
      

Problem Description

You are given a string dominoes representing a row of dominoes. Each character can be:

• 'L': A domino pushed to the left
• 'R': A domino pushed to the right
• '.': A domino standing upright

The task is to return a string representing the final state of all dominoes after all movements have stopped. Each domino can only be pushed once per direction, and the process continues until a stable state is reached.

Thought Process

At first glance, it seems like we need to simulate each second of the dominoes falling, updating the string repeatedly until it stabilizes. This brute-force simulation would be inefficient for large inputs, as it may require many passes.

However, if we think about the problem in terms of "forces" applied to each domino from left and right, we can model the final state more efficiently. Instead of simulating every step, we can calculate, for each domino, the net force applied from the left and the right, and decide the final state based on which force is stronger.

The key insight is to recognize that the effect of a push decreases as we move further from the source, and if equal forces meet, the domino stays upright. By using arrays to record these forces, we can determine the outcome in a single pass from each direction.

Solution Approach

We use a two-pass algorithm to compute the net force on each domino:

1. First Pass (Left to Right):
   • Initialize a force variable to 0.
   • Iterate from left to right:
   • If the domino is 'R', set force to n (maximum).
   • If the domino is 'L', set force to 0.
   • If the domino is '.', decrement force by 1 (not below 0).
   • Add the current force to a forces array at each index.
2. Second Pass (Right to Left):
   • Reset the force variable to 0.
   • Iterate from right to left:
   • If the domino is 'L', set force to n.
   • If the domino is 'R', set force to 0.
   • If the domino is '.', decrement force by 1 (not below 0).
   • Subtract the current force from the forces array at each index.
3. Final State:
   • For each domino, if the net force is positive, it falls right ('R').
   • If the net force is negative, it falls left ('L').
   • If the net force is zero, it remains upright ('.').

This approach is efficient because each domino is processed only twice, and the final state is determined in a single pass.

Example Walkthrough

Let's walk through the example dominoes = ".L.R...LR..L..":

1. Left to Right Pass:
   • Start with force = 0.
   • At index 1 ('L'), force is set to 0.
   • At index 3 ('R'), force is set to n=13.
   • Next dominoes after 'R' get decreasing force: 12, 11, etc., until interrupted by another 'L' or force drops to 0.
2. Right to Left Pass:
   • Start with force = 0.
   • At index 12 ('L'), force is set to 13.
   • Previous dominoes before 'L' get decreasing negative force: -12, -11, etc., until interrupted by another 'R' or force drops to 0.
3. Combine Forces:
   • At each position, add left-to-right and subtract right-to-left force.
   • Decide final state: positive = 'R', negative = 'L', zero = '.'.
4. Result:
   • Final string: "LL.RR.LLRRLL.."

Time and Space Complexity

• Brute-force Simulation:
  • Time: O(n^2) in worst case, since each pass may change only a few dominoes, requiring many iterations.
  • Space: O(n) for the string or list representation.
• Optimized "Force" Approach:
  • Time: O(n), since we make two linear passes and one final pass to build the result.
  • Space: O(n), for the forces array.

The optimized approach is much faster and suitable for large inputs.

Summary

The Push Dominoes problem can be solved efficiently by thinking in terms of forces instead of simulating the process step-by-step. By making two linear passes to calculate the net force on each domino, we can determine the final state quickly and elegantly. This approach leverages the idea that the influence of a push diminishes with distance and can be modeled numerically, making the solution both efficient and easy to understand.