Push Dominoes

Push Dominoes

What is this problem about?

The Push Dominoes problem gives you a string of dominoes: 'L' falls left, 'R' falls right, '.' is standing. After all dominos fall, determine the final state. This coding problem uses a two-pointer simulation or DP approach to propagate forces from both directions. The two pointers, string, and dynamic programming interview pattern is the core.

Why is this asked in interviews?

Microsoft, Meta, Amazon, Google, and Bloomberg ask this because it requires modeling opposing forces meeting in the middle — a spatial reasoning challenge. The elegant two-pointer approach processes forces from 'R' and 'L' boundaries.

Algorithmic pattern used

Force propagation. Assign a force to each position based on nearest 'R' (positive force, decreasing) and nearest 'L' (negative force, decreasing). Net force at each position: if positive → 'R', negative → 'L', zero → '.'. Two-pass approach: left-to-right assigns rightward forces, right-to-left assigns leftward forces. Or use segment-by-segment analysis: for each region between anchors (R...L, L...R, R...R, L...L), apply rules.

Example explanation

s="R..L".

• 'R' pushes right with force n, decreasing by 1 per position.
• 'L' pushes left similarly.
• Position 1 (between R and L): R-force=2, L-force=2 → tie → '.'.
• Position 2: R-force=1, L-force=3 → L-force wins → 'L'. Wait, let me recalculate for "R..L" (length 4): Positions: R(force3),.(force2),.(force1→vs1),L. Between R and L: forces [3,2,1] from R and [1,2,3] from L.
• pos1: R=3-1=2, L=3-2=1? No... For "R..L": pos0=R, pos1=R-force=2, pos2=tie(L=2,R=1)→'L', pos3=L. Result: "RRLL".

Common mistakes candidates make

• Not handling tied forces (should remain '.').
• Confusing the force propagation direction.
• Not resetting forces when encountering an anchor ('R' or 'L').
• Off-by-one in force assignment.

Interview preparation tip

Push Dominoes is a spatial force propagation problem. The cleanest implementation: iterate through segments between R and L anchors. For "R...L" segment: fill positions from both ends toward center, stopping when forces meet. For "R...R": all fall right. For "L...L": all fall left. For "L...R": all stand upright. Practice force/influence propagation problems: "candles lighting," "wave propagation," "light spreading" — they all use similar two-pass or segment analysis approaches.