Skip to main content

838 - Push Dominoes

Difficulty: Medium | Pattern: Two Pointers / Simulation | Company tags: Amazon, Google

Problem Statement​

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, a domino that is falling to the left pushes the adjacent domino on the left. Similarly, a domino that is falling to the right pushes the adjacent domino 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.

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
  • dominoes[i] = '.' if the i-th domino has not been pushed

Return a string representing the final state.

Example:

Input: dominoes = "RR.L"
Output: "RR.L"  (middle '.' is balanced by R and L)

Example 2:

Input: dominoes = ".L.R...LR...L"
Output: "LL.RRR.LLRRRL"

Approach: Forces — O(n), O(n)​

Key insight: Compute net force on each domino. A right force of magnitude n - i decreases by 1 per step. Left force similarly. Final state: positive → R, negative → L, zero → '.' (balanced).

Algorithm Flow​

def pushDominoes(dominoes: str) -> str:
    n = len(dominoes)
    forces = [0] * n
    
    # Right forces
    force = 0
    for i in range(n):
        if dominoes[i] == 'R':
            force = n
        elif dominoes[i] == 'L':
            force = 0
        else:
            force = max(0, force - 1)
        forces[i] += force
    
    # Left forces (subtract)
    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(0, force - 1)
        forces[i] -= force
    
    return ''.join('R' if f > 0 else 'L' if f < 0 else '.' for f in forces)

Dry Run​

dominoes = "RR.L"

Right forces: R→4, R→4, .→3, L→0: [4,4,3,0] Left forces (reversed): L→4, .→3, R→0, R→0: subtract [0,0,3,4] Net: [4,4,0,-4] → "RR.L" ✓

Complexity​

  • Time: O(n)
  • Space: O(n)

Key Terms​

TermDefinition
Net forceThe combined push on a domino from the nearest right-pushing and left-pushing forces, decayed by distance.
Force decayA force's magnitude drops by 1 per position traveled from its source, modeling how a nearer push reaches a domino before a farther one.
SimulationDirectly modeling the physical process (or an equivalent computed proxy) instead of tracking events over time.
Two-pass scanComputing left-to-right and right-to-left contributions separately, then combining them.
Balance pointA domino equidistant from an 'R' and an 'L' remains upright ('.') because forces cancel.

FAQ​

Q: Can this be solved without the O(n) forces array? A: Yes — an alternative is to split the string on stable dominoes and process each R...L, L...R, R..., ...L segment independently in O(1) extra space per segment, still O(n) overall but without a full auxiliary array.

Q: What if the input is empty or has no 'R'/'L' at all? A: An empty string returns empty; a string of only '.' characters returns itself unchanged since no forces are ever applied.

Q: How does the algorithm handle "RL" (adjacent opposite pushes) vs "LR"? A: "RL" stays "RL" — both dominoes are already fully pushed toward each other and don't move further. "LR" stays "LR" since they lean away from each other and never interact.

Q: What if multiple dominoes are pushed simultaneously in the same direction, like "RR...LL"? A: The forces from the two 'R's and two 'L's are simply computed independently per position; the closest source dominates via the decay/reset logic, so consecutive same-direction pushes just extend the influence window.

Q: What's the follow-up interviewers usually ask? A: "Can you do it with O(1) extra space?" — yes, by using two pointers to find segment boundaries between fixed dominoes and filling each segment directly based on its boundary characters.

Quick Revision​

  • Pattern: simulate net force per cell using two linear passes instead of literally simulating time steps.
  • Left-to-right pass computes rightward force: resets to n at 'R', drops to 0 at 'L', decays by 1 at '.'.
  • Right-to-left pass computes leftward force the same way, then subtracts it from the stored value.
  • Final cell state: positive net force → 'R', negative → 'L', zero → '.' (balanced).
  • Equivalent alternative approach: split string by stable ('R' or 'L') dominoes into segments and resolve each segment by its boundary pair.
  • "RL" segments freeze as-is; "LR" segments freeze as-is; "RR" or "LL" fully propagate.
  • Time complexity O(n), space O(n) for the forces array (or O(1) with the segment-pointer approach).
  • Edge cases: empty string, all dots, single character, adjacent opposite pushes.
  • 42 - Trapping Rain Water (LeetCode) — same two-pass, left/right contribution accumulation pattern.
  • 921 - Minimum Add to Make Parentheses Valid (LeetCode) — another string simulation solved via a single forward/backward scan rather than literal step simulation.