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.
In this approach, we simulate the forces acting on the dominoes as a one-dimensional array of forces. Initially, each domino has zero force. We perform two passes: from left to right, and then from right to left. In the first pass, we apply forces caused by 'R' and increase the force gradually by 1 for each subsequent domino. In the second pass, we apply forces caused by 'L' and decrease the force by 1 for each subsequent domino. Finally, the resultant force at each position determines whether the domino remains upright (force=0), falls to the right (force>0), or falls to the left (force<0).
The function uses a two-pass scanning to compute the forces acting on each domino. It first collects forces exerted by 'R's as positive values and reduces them across dominoes. Then, it collects forces exerted by 'L's as negative values, reducing these forces as well. By summing these forces, we decide the final state of each domino based on the net force.
Python
C
JavaScript
Time complexity: O(n), where n is the number of dominoes since we traverse the dominoes twice.
Space complexity: O(n) due to the 'forces' array.
This approach is also efficient and leverages a queue to process and simulate the domino effect until stability. We maintain a queue that handles dominos that need to be processed next, checking to apply the effect of the nearest 'L' or 'R'. This is somewhat similar to breadth-first search (BFS) in tree/graph traversal.
This solution uses a queue to simulate the domino fall process by looking through each 'R' or 'L' in the sequence and checking subsequent dominoes, applying rules as necessary (balancing too). As dominoes fall, they are added to the queue until all possibilities are exhausted.
Time complexity: O(n), since each domino movement is processed exactly once.
Space complexity: O(n), due to the queue storing no more than all domino positions.
Treat all initially pushed dominoes (L or R) as sources, which simultaneously propagate their forces outward. Use a queue to perform BFS layer by layer (0, 1, 2, ...):
We define time[i] to record the first moment when the i-th domino is affected by a force, with -1 indicating it has not been affected yet. We also define force[i] as a variable-length list that stores the directions ('L', 'R') of forces acting on the domino at the same moment. Initially, push all indices of L/R dominoes into the queue and set their time to 0.
When dequeuing index i, if force[i] contains only one direction, the domino will fall in that direction f. Let the index of the next domino be:
$
j =
\begin{cases}
i - 1, & f = L,\
i + 1, & f = R.
\end{cases}
If 0 leq j < n:
, it means j has not been affected yet. Record time[j] = time[i] + 1, enqueue it, and append f to force[j]., it means j has already been affected by another force at the same "next moment." In this case, append f to force[j], causing a standoff. Subsequently, since len(force[j]) = 2, it will remain upright.After the queue is emptied, all positions where force[i] has a length of 1 will fall in the corresponding direction, while positions with a length of 2 will remain as .. Finally, concatenate the character array to form the answer.
The complexity is O(n), and the space complexity is O(n), where n$ is the number of dominoes.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Two Pass Force Calculation | Time complexity: O(n), where n is the number of dominoes since we traverse the dominoes twice. |
| Approach 2: Simulate using Queue | Time complexity: O(n), since each domino movement is processed exactly once. |
| Multi-Source BFS | — |
| 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. |
Push Dominoes - Leetcode 838 - Python • NeetCode • 29,064 views views
Watch 9 more video solutions →Practice Push Dominoes with our built-in code editor and test cases.
Practice on FleetCode