MediumTwo PointersStringDynamic ProgrammingUpdated Sep 2026

838. Push Dominoes

Asked at Anduril

Difficulty

Medium

Time

O(n)

Space

O(n)

Pattern

Two Pointers

Companies

1

Problem

You are given a row of dominoes as a string. Each character is 'L' (this domino was pushed to the left), 'R' (pushed to the right), or '.' (not pushed, standing upright).

All pushes happen at the same time. Every second, a falling domino knocks over its neighbour: an L domino pushes the domino on its left, and an R domino pushes the domino on its right. A domino that is already falling or already down does not pass on any extra force. If a standing domino is hit from the left and the right at the same moment, the two forces cancel and it stays standing.

Return the final string after everything has settled. Positions that end up falling left become 'L', positions that fall right become 'R', and positions that never fall stay '.'.

Forces from both sides

dominoesRR.L0123?The dot at index 2 is hit from both sides at once
In "RR.L" the middle domino is pushed right by the second R and left by the L at the same second, so it stays standing.

Constraints

  • ●1 <= dominoes.length <= 10^5
  • ●dominoes[i] is 'L', 'R', or '.'

Examples

Example 1
Inputdominoes = "RR.L"
OutputRR.L
WhyThe first two dominoes were pushed right, so they stay 'R'. The last one was pushed left, so it stays 'L'. The middle domino is hit from the left by the second 'R' and from the right by the 'L' at the same second, so the forces cancel and it stays '.'.
Example 2
Inputdominoes = ".L.R...LR..L.."
OutputLL.RR.LLRRLL..
WhyThe 'L' at index 1 pulls the first domino left, giving 'LL'. The 'R' at index 3 pushes everything to its right until it meets the 'L' at index 7; they meet in the middle, so index 5 falls right and index 6 falls left, leaving index 4 as '.'. The last 'L' at index 11 pulls the dominoes at 9 and 10 to
Example 3
Inputdominoes = "R."
OutputRR
WhyThe 'R' at index 0 pushes the standing domino at index 1 to the right, so both end up as 'R'.

Asked At

1 companies
CompanyDifficulty
AndurilMediumView all Anduril questions →

How to Think About It

1

Second-by-second simulation is O(n²) in the worst case.

2

Key insight: for each standing domino, only two things matter — how far away the nearest R is to its left (with no L in between), and how far away the nearest L is to its right (with no R in between). The closer push wins; a tie means it stays standing.

3

Implement it as forces: sweep left to right, setting a large force n at each R, decreasing by 1 each step, and resetting to 0 at each L. Sweep right to left for L the same way. The net force right - left decides each domino.

4

Positive net means R, negative means L, zero means ..

5

Walkthrough for "RR.L": rightward forces [4,4,3,0]; leftward forces [0,0,3,4]. Net [4,4,0,-4] -> "RR.L" (the middle domino is hit from both sides at once).

Optimal Approach

Step 1: forces = [0] * n.
Step 2: Left to right with f = 0: at R set f = n; at L set f = 0; at . set f = max(f - 1, 0). Add f to forces[i].
Step 3: Right to left with f = 0: at L set f = n; at R set f = 0; at . decrement. Subtract f from forces[i].
Step 4: Map each force to R (positive), L (negative), or . (zero).

Time: O(n). Space: O(n).

Two sweeps, then compare forces

right force44300123Left-to-right sweep: R resets the force to n, then itdrops by 1 each stepleft force00340123Right-to-left sweep: L resets the force to n, then itdrops by 1 each stepnet440-40123Net = right − left; positive means R, negative meansL, zero means it stays '.'net > 0 → Rnet < 0 → Lnet = 0 → .
Sweep right for R forces, sweep left for L forces, then let the sign of the net force decide each domino.
ComplexityTime O(n)Space O(n)Two linear sweeps plus one output pass; the extra array of net forces costs O(n) memory.

What Trips People Up in Real Interviews

1

Forgetting that an opposite push blocks a force. An L stops a rightward push from continuing past it.

2

Treating equal-distance pushes as one side winning. Balanced pushes leave the domino standing.

3

Simulating by repeatedly rebuilding the string until it stops changing — correct but quadratic.

4

Starting the force at a small constant. It must be larger than any distance (use n) so it never decays to zero too early.

Solution Code

O(n) time
def pushDominoes(dominoes):
    n = len(dominoes)
    forces = [0] * n
    f = 0
    for i in range(n):
        ch = dominoes[i]
        if ch == 'R':
            f = n
        elif ch == 'L':
            f = 0
        else:
            f = max(f - 1, 0)
        forces[i] += f
    f = 0
    for i in range(n - 1, -1, -1):
        ch = dominoes[i]
        if ch == 'L':
            f = n
        elif ch == 'R':
            f = 0
        else:
            f = max(f - 1, 0)
        forces[i] -= f
    return ''.join('R' if x > 0 else 'L' if x < 0 else '.' for x in forces)

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Push Dominoes problem?

Push Dominoes gives you a row of dominoes, each pushed left (`L`), pushed right (`R`), or standing (`.`), and asks for the final state after they all fall. A standing domino hit from both sides at the same time stays up. Simulating second by second works, but a two-pass force calculation is cleaner and linear.

How do you solve Push Dominoes?

The optimal approach runs in O(n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Push Dominoes?

Push Dominoes is asked at Anduril. It is a medium difficulty problem.

What are common mistakes on Push Dominoes?
  • Forgetting that an opposite push blocks a force. An `L` stops a rightward push from continuing past it.
  • Treating equal-distance pushes as one side winning. Balanced pushes leave the domino standing.
  • Simulating by repeatedly rebuilding the string until it stops changing — correct but quadratic.
  • Starting the force at a small constant. It must be larger than any distance (use `n`) so it never decays to zero too early.