Problem Overview
LeetCode 838 — Push Dominoes — gives you a string dominoes where each character is L (pushed left), R (pushed right), or . (standing upright). Simultaneously, each pushed domino exerts force on its neighbor. Return the final state of all dominoes after they stop falling.
The physics are simultaneous: all forces propagate at the same speed. A domino pushed left pushes its left neighbor, which pushes its left neighbor, and so on. When opposing forces meet at the same time, the domino in the middle stays upright. This simultaneous resolution is what makes the problem tricky.
There are two main approaches: BFS simulation (process forces level by level) and the segment approach (process each gap between forced dominoes independently). The segment approach is more elegant and runs in a single O(n) pass.
- Input: string of characters L, R, and . (dot)
- L pushes left, R pushes right, dot is upright
- All forces propagate simultaneously at equal speed
- Equal opposing forces cancel — domino stays upright
- Return the final string after all dominoes settle
The Segment Processing Approach
The key insight is to add virtual sentinels: prepend L and append R to the string. Then scan for consecutive pairs of forced dominoes and process the segment of dots between them. There are exactly four cases based on the left and right forces bounding each segment.
Case 1: L...L — all dots fall left. The left force from the right boundary pushes everything leftward with no opposition. Case 2: R...R — all dots fall right. The right force from the left boundary pushes everything rightward. These two cases are straightforward.
Case 3: L...R — no force reaches the dots. The left force pushes away from the segment and the right force also pushes away. The dots between them stay upright. Case 4: R...L — forces collide from both sides. Dots near the left boundary fall right, dots near the right boundary fall left, and the middle dot (if the gap is odd) stays upright.
Sentinel Trick
Adding L at the start and R at the end eliminates edge cases for dots at the beginning or end of the string. The sentinels create natural boundaries without affecting the answer since they only influence dots that would otherwise have no force.
Resolving R...L Collisions
The R...L case is the most interesting. If there are k dots between R and L, the first k/2 dots fall right (pushed by R) and the last k/2 dots fall left (pushed by L). If k is odd, the middle dot stays upright because the equal opposing forces cancel.
Use two pointers: one advancing from the left boundary rightward setting dots to R, and one advancing from the right boundary leftward setting dots to L. Stop when the pointers meet or cross. If they meet at the same position, that dot stays as a dot.
This collision resolution runs in O(k) time for a segment of k dots. Since all segments are disjoint and their total length is n, the entire algorithm processes all segments in O(n) time combined.
Step-by-Step Walkthrough
Consider dominoes = ".L.R...LR..L..". Add sentinels: "L.L.R...LR..L..R". Now scan for pairs of forced characters and process each segment.
Segment "L.L": L...L pattern with 1 dot — falls left → "LL". Segment "L.R": L...R pattern with 1 dot — stays upright → ".". Segment "R...L": R...L with 3 dots — first 1 falls R, last 1 falls L, middle stays → "R.L". Segment "LR": adjacent, no dots. Segment "R..L": R...L with 2 dots — first 1 falls R, last 1 falls L → "RL". Segment "L..R": L...R with 2 dots — stay upright → "..".
Combining all segments (removing sentinels): "LL.RR.LLRRLL..". This matches the expected output. Each segment was processed independently in constant time per dot.
BFS Alternative
The BFS approach simulates forces level by level using a queue. Initially enqueue all L and R positions. Each step, propagate forces one position. When two forces arrive at the same dot simultaneously, they cancel. BFS is more intuitive but uses O(n) queue space.
Implementation in Python and Java
In Python, convert the string to a list for mutation. Find indices of all L and R characters (plus sentinels). Iterate through consecutive pairs and apply the four-case logic. The R...L case uses a while loop with two pointers converging from both ends.
In Java, use a char[] array for the result. The logic is identical. Find forced positions, iterate pairs, and fill in each segment. The two-pointer collision resolution in the R...L case translates directly from Python.
An alternative clean implementation: compute a force array where each cell stores the net force (positive for rightward, negative for leftward). Scan left-to-right accumulating R forces (decaying by 1 per step), then right-to-left accumulating L forces. The sign of the net force determines each domino's direction.
Complexity Analysis
Time complexity is O(n) for the segment approach. We scan the string once to find forced positions, then process each segment in time proportional to its length. All segments are disjoint, so total work is O(n).
Space complexity is O(n) for the output array (or list). The segment approach uses O(1) additional space beyond the output. The BFS alternative also uses O(n) space for the queue but has a larger constant factor.
Both approaches are optimal since we must read every character and write every character in the output. The segment approach is preferred in interviews for its elegance and minimal space usage.
YeetCode Flashcard Tip
Push Dominoes combines simulation thinking with the two-pointer technique. Add it to your YeetCode deck alongside Trapping Rain Water and Asteroid Collision for a complete force-simulation practice set.