Push Dominoes
Asked at Anduril
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Anduril | Medium | View all Anduril questions → |
How to Think About It
Second-by-second simulation is O(n²) in the worst case.
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.
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.
Positive net means R, negative means L, zero means ..
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).
What Trips People Up in Real Interviews
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.
Solution Code
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)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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.