Back to solutions

Push Dominoes

MediumArrays

Find the final resting state of a row of pushed dominoes.

Open problem
Constraints
  • 1 <= length <= 10^5
  • characters are 'L', 'R', or '.'

Force accumulation from both sides

Time O(n)Space O(n)

Assign each cell a signed force. Sweep left to right: an 'R' injects a large positive force that decays by one each upright step; an 'L' resets it. Sweep right to left subtracting a symmetric force for 'L'. The final sign of each cell's net force decides L, R, or upright (zero).

Key terms
force decay:
The push weakens by one for each empty cell it travels, modelling distance.
net force:
Positive means rightward wins, negative leftward, zero means balanced (upright).
string pushDominoes(string d) {
    int n = d.size(); vector<int> f(n, 0); int force = 0;
    for (int i = 0; i < n; i++) {
        if (d[i] == 'R') force = n; else if (d[i] == 'L') force = 0; else force = max(force - 1, 0);
        f[i] += force;
    }
    force = 0;
    for (int i = n - 1; i >= 0; i--) {
        if (d[i] == 'L') force = n; else if (d[i] == 'R') force = 0; else force = max(force - 1, 0);
        f[i] -= force;
    }
    string res(n, '.');
    for (int i = 0; i < n; i++) res[i] = f[i] > 0 ? 'R' : f[i] < 0 ? 'L' : '.';
    return res;
}
Step by step
  1. Left-to-right: track a rightward force, set to max at 'R', zero at 'L', decaying otherwise; add it to each cell.
  2. Right-to-left: track a leftward force similarly and subtract it from each cell.
  3. For each cell, positive net force becomes 'R', negative becomes 'L', zero stays '.'.
  4. Return the assembled string.