Push Dominoes: Force Simulation Explained

You have a row of dominoes, some pushed left, some pushed right, and others still standing. After enough time passes, every domino settles into a final state. Your job is to figure out what that final state looks like. This is LeetCode 838: Push Dominoes, rated medium. The trick is to avoid simulating second by second and instead assign forces that propagate through the row in two passes.

The problem

You are given a string dominoes of length n. Each character is one of:

• 'L': this domino was pushed to the left
• 'R': this domino was pushed to the right
• '.': this domino is standing upright

Dominoes that are pushed will knock over adjacent standing dominoes. If a domino receives equal force from both sides at the same time, it stays standing. Return the final state of all dominoes as a string.

dominoes = ".L.R...LR..L.."
# Output: "LL.RR.LLLLLL.."

The force simulation approach

The key insight is to model the push as a force that decays over distance. When you see an 'R', it exerts force on everything to its right, but that force weakens the farther it travels. Similarly, an 'L' exerts decaying force to the left. At each position, you compare the rightward force against the leftward force. Whichever is stronger wins, and if they are equal, the domino stays upright.

Here is how to make this concrete. Use N as the total length of the string. Scan left to right to compute rightward forces: when you hit an 'R', assign force N at that position. For every subsequent '.', the force decays by 1. When you hit an 'L' or another 'R', reset appropriately. Then scan right to left to compute leftward forces using the same logic. At each position, subtract the leftward force from the rightward force. A positive result means the domino falls right, a negative result means it falls left, and zero means it stays standing.

Step-by-step walkthrough

Let's trace through a small example with dominoes = "R.L" to see how the two passes work together.

The R at index 0 pushes rightward with decaying force. The L at index 2 pushes leftward with decaying force. At index 1, both forces are equal, so the domino stays standing. The output is "R.L", which matches the expected behavior: the middle domino is caught between two equal and opposite forces.

The code

def pushDominoes(dominoes):
    n = len(dominoes)
    forces = [0] * n

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

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

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

The first loop scans left to right, building rightward forces. Every time it encounters 'R', the force resets to n. On a dot, the force decays by 1 (never going below 0). On 'L', the force resets to 0 because a leftward domino blocks rightward propagation.

The second loop scans right to left, building leftward forces in the same way and subtracting them from the accumulated rightward forces. After both passes, each position holds the net force. Positive means right wins, negative means left wins, and zero means the domino stays upright.

Complexity analysis

Time: O(n). Two linear passes through the string, plus one pass to build the result. Each pass visits every character exactly once.

Space: O(n). The forces array and the result list each use O(n) space.

The brute force approach simulates each second, pushing dominoes one step at a time until nothing changes. In the worst case (all dots with R at the start), you need O(n) rounds, each scanning O(n) positions. The force-based approach collapses all of that into two passes.

The building blocks

Two-pass force propagation

The core pattern here is assigning decaying values from a source and scanning in both directions. You see this same structure in other problems. In Trapping Rain Water, each pass tracks the running max height from one direction, and you combine them with min. In Candy, each pass ensures neighbor constraints from one direction, and you combine them with max. In Push Dominoes, you combine with subtraction.

The general skeleton looks like this:

forward = [0] * n
for i in range(n):
    if source_condition(i):
        forward[i] = initial_value
    else:
        forward[i] = decay(forward[i - 1])

backward = [0] * n
for i in range(n - 1, -1, -1):
    if source_condition(i):
        backward[i] = initial_value
    else:
        backward[i] = decay(backward[i + 1])

result = combine(forward, backward)

What varies across problems is the initial value, the decay function, and the combination operation. Recognizing this template lets you solve each new problem by just filling in those three blanks.

Edge cases

Before submitting, make sure your solution handles these:

• All dots ".....": no forces at all, everything stays standing. Output matches input.
• All same direction "RRR": every position gets rightward force, no leftward force. Output is "RRR".
• R and L collide "R...L": forces meet in the middle. If the gap is odd, the center stays as a dot. If the gap is even, the two forces meet exactly between two positions and both fall.
• L then R "L...R": the L pushes left and the R pushes right. They move away from each other, so the dots between them are unaffected. Output is "L...R".
• Adjacent RL "RL": R pushes right but L is already there. No dots to affect. Output is "RL".
• Single character ".", "L", or "R": output matches input.

From understanding to recall

You have seen how force simulation turns a messy multi-step simulation into two clean linear passes. The logic is simple: assign decaying forces from each direction and compare. But when you sit down in an interview, will you remember to use n as the force magnitude? Will you remember that 'L' resets rightward force to zero and vice versa?

These details are easy to confuse under pressure. Spaced repetition helps you move the pattern from "understood" to "automatic." You practice writing the two-pass force loop from scratch, and each review interval gets longer. After a few rounds, the code flows without hesitation.

The two-pass propagation pattern is one of the most versatile building blocks in competitive programming. Learning it once and drilling it with spaced repetition means you can handle Candy, Trapping Rain Water, Push Dominoes, and many other problems without rethinking the approach from scratch every time.

Related posts

• Trapping Rain Water - Two-pass prefix max approach for computing trapped water at each position
• Longest Palindromic Substring - Expand-around-center technique that also processes strings from multiple directions
• Container With Most Water - Two-pointer greedy that shrinks the window based on which side is shorter

CodeBricks breaks the push dominoes problem into its two-pass force propagation building block, then drills it independently with spaced repetition. You type the force-assignment loop from scratch until the pattern is automatic. When a two-pass simulation question appears in your interview, you do not hesitate. You just write it.