Watch 10 video solutions for Push Dominoes, a medium level problem involving Two Pointers, String, Dynamic Programming. This walkthrough by NeetCode has 29,064 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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, each domino that is falling to the left pushes the adjacent domino on the left. Similarly, the dominoes falling to the right push their adjacent dominoes standing 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.
For the purposes of this question, we will consider that a falling domino expends no additional force to a falling or already fallen domino.
You are given a string dominoes representing the initial state where:
dominoes[i] = 'L', if the ith domino has been pushed to the left,dominoes[i] = 'R', if the ith domino has been pushed to the right, anddominoes[i] = '.', if the ith domino has not been pushed.Return a string representing the final state.
Example 1:
Input: dominoes = "RR.L" Output: "RR.L" Explanation: The first domino expends no additional force on the second domino.
Example 2:
Input: dominoes = ".L.R...LR..L.." Output: "LL.RR.LLRRLL.."
Constraints:
n == dominoes.length1 <= n <= 105dominoes[i] is either 'L', 'R', or '.'.Problem Overview: You get a string representing dominoes. Each character is 'L', 'R', or '.'. When a domino falls left or right, it pushes the next domino in that direction. The task is to compute the final state after all forces propagate and the system stabilizes.
Approach 1: Two Pass Force Calculation (O(n) time, O(n) space)
This approach models the force exerted by falling dominoes. Scan the array from left to right and track the influence of 'R' pushes. Each step decreases the force as it moves away from the source. Store this force in an array. Then run a second pass from right to left to track 'L' forces. Subtract the right force from the left force at each index. Positive values mean right push wins, negative values mean left push wins, and zero means the domino remains upright. The method works because each domino only depends on the nearest pushing force in either direction. Complexity stays O(n) time with O(n) auxiliary space for the force array.
This technique relies on simple array scans and works well for problems involving directional influence across a string. The two directional sweeps resemble a two pointers pattern where influence propagates from both ends.
Approach 2: Simulate using Queue (O(n) time, O(n) space)
This approach treats the process as a time-based simulation. Start by pushing all initially falling dominoes ('L' and 'R') into a queue with their index and direction. Process the queue using a BFS-style loop. When a domino falls, it attempts to push its neighbor. If the neighbor is upright ('.'), mark it with the direction and enqueue it for the next step. Conflicts happen when two forces reach a domino simultaneously from opposite directions; in that case the domino stays upright. The queue ensures events are processed in chronological order, making the simulation accurate and still linear in time.
The queue-based simulation mirrors propagation problems often solved with dynamic programming style state updates or BFS expansion. It is intuitive and easier to reason about when visualizing the domino effect.
Recommended for interviews: The two-pass force calculation is typically preferred. It runs in linear time, uses simple arrays, and avoids explicit simulation. Interviewers like it because it demonstrates pattern recognition and efficient traversal. The queue simulation is still valuable since it mirrors the real physical process and clearly handles conflicts between opposing forces.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Pass Force Calculation | O(n) | O(n) | Best general solution. Efficient linear scan and commonly expected in interviews. |
| Queue Simulation (BFS) | O(n) | O(n) | Good when modeling time-based propagation or explaining the physical domino process clearly. |