LeetCode 838: Push Dominoes

Problem Restatement

We are given a string dominoes.

Each character describes the initial state of one domino:

After each second, a falling domino pushes the adjacent upright domino in the same direction.

If a standing domino receives equal force from both sides at the same time, it stays upright.

A domino already falling or already fallen does not pass extra force through another falling domino.

Return the final state of all dominoes. The constraints allow strings up to length 10^5.

Input and Output

Function shape:

class Solution:
    def pushDominoes(self, dominoes: str) -> str:
        ...

Examples

Example 1:

dominoes = "RR.L"

The final state is:

"RR.L"

The left "R" side does not push through an already falling domino, so the middle state stays as given.

Example 2:

dominoes = ".L.R...LR..L.."

The final state is:

"LL.RR.LLRRLL.."

First Thought: Simulate Every Second

A direct approach is to simulate time.

At each second:

1. Look at every upright domino.
2. Check whether it is pushed from the left, from the right, or both.
3. Build the next state.
4. Repeat until nothing changes.

This can work for small strings, but it is too slow.

A force may travel across a long row of dots. With n dominoes, simulation can take many rounds, and each round scans the string.

That can become:

O(n^2)

We need a linear method.

Key Insight

A domino’s final state depends on the nearest effective force from the left and the nearest effective force from the right.

A right-pushing force "R" travels to the right until blocked by an "L".

A left-pushing force "L" travels to the left until blocked by an "R".

We can compute net force with two scans:

1. Left to right: measure force from "R".
2. Right to left: measure force from "L".

If the right force is stronger, the domino becomes "R".

If the left force is stronger, the domino becomes "L".

If they are equal, the domino stays ".".

Algorithm

Let n = len(dominoes).

Create an array forces of length n, initially all 0.

First pass from left to right:

1. If we see "R", set force to n.
2. If we see "L", reset force to 0.
3. If we see ".", decrease force by 1, but not below 0.
4. Add this force to forces[i].

Second pass from right to left:

1. If we see "L", set force to n.
2. If we see "R", reset force to 0.
3. If we see ".", decrease force by 1, but not below 0.
4. Subtract this force from forces[i].

Finally:

Walkthrough

Use:

dominoes = "R...L"

The "R" pushes right.

The "L" pushes left.

Positions:

0 1 2 3 4
R . . . L

The middle dot at index 2 receives equal force from both sides.

Final state:

"RR.LL"

Index 1 is closer to "R", so it becomes "R".

Index 3 is closer to "L", so it becomes "L".

Index 2 is equally close to both, so it stays ".".

Correctness

The left-to-right pass computes, for each position, the strength of the nearest unblocked "R" force coming from the left.

When the scan sees "R", a new rightward force begins. When it sees "L", that rightward force is blocked. Between them, the force decreases by one per position, matching the one-cell-per-second propagation rule.

The right-to-left pass computes the analogous nearest unblocked "L" force from the right.

For each domino, the final direction is determined by comparing these two arrival strengths. A larger rightward force means the "R" wave arrives earlier, so the domino falls right. A larger leftward force means the "L" wave arrives earlier, so the domino falls left. Equal force means both waves arrive at the same time, so the domino stays upright.

Thus the algorithm assigns every domino exactly the final state implied by the simultaneous process.

Complexity

Implementation

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

        force = 0
        for i, ch in enumerate(dominoes):
            if ch == "R":
                force = n
            elif ch == "L":
                force = 0
            else:
                force = max(force - 1, 0)

            forces[i] += force

        force = 0
        for i in range(n - 1, -1, -1):
            ch = dominoes[i]

            if ch == "L":
                force = n
            elif ch == "R":
                force = 0
            else:
                force = max(force - 1, 0)

            forces[i] -= force

        result = []

        for force in forces:
            if force > 0:
                result.append("R")
            elif force < 0:
                result.append("L")
            else:
                result.append(".")

        return "".join(result)

Code Explanation

The force array stores the net force at each position:

forces = [0] * n

In the left-to-right pass:

if ch == "R":
    force = n
elif ch == "L":
    force = 0
else:
    force = max(force - 1, 0)

An "R" starts a strong rightward force.

An "L" blocks rightward force.

A dot receives the previous force weakened by one.

We add that rightward force:

forces[i] += force

In the right-to-left pass, we do the same for leftward force, but subtract it:

forces[i] -= force

Finally, positive net force becomes "R", negative net force becomes "L", and zero becomes ".".

Testing

def run_tests():
    s = Solution()

    assert s.pushDominoes("RR.L") == "RR.L"
    assert s.pushDominoes(".L.R...LR..L..") == "LL.RR.LLRRLL.."
    assert s.pushDominoes("R...L") == "RR.LL"
    assert s.pushDominoes("R..L") == "RRLL"
    assert s.pushDominoes("...") == "..."
    assert s.pushDominoes("L....") == "L...."
    assert s.pushDominoes("....R") == "....R"

    print("all tests passed")

run_tests()

Test meaning: