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 '.'.The key idea in #838 Push Dominoes is to simulate how forces propagate across the domino line. Each domino can be influenced by a push from the left (L) or the right (R). A common strategy is to analyze the segments between non-dot characters and determine how the dominoes in between should fall.
One effective method uses a two-pointer technique. Traverse the string while tracking the last seen force and the next force. If the pattern is L...L or R...R, all dominoes in between fall in the same direction. If it is R...L, dominoes fall inward from both sides. For L...R, the middle dominoes remain upright because the forces move away from each other.
Another perspective treats the pushes as force propagation, computing influence from left-to-right and right-to-left and combining them to determine the final state. Both approaches run in linear time since each domino is processed a constant number of times.
Overall, the optimal solution achieves O(n) time complexity with O(n) or O(1) extra space depending on the implementation.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Two-Pointer Segment Analysis | O(n) | O(1) |
| Force Propagation (Left & Right Influence Arrays) | O(n) | O(n) |
NeetCode
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).
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.
1def pushDominoes(dominoes):
2 n = len(dominoes)
3 forces = [0] * n
4
5 # Calculate right forces
6 force = 0
7 for i in range(n):
8 if dominoes[i] == 'R':
9 force = n # A large force imposed by R
10 elif dominoes[i] == 'L':
11 force = 0 # No force given by L
12 else:
13 force = max(force - 1, 0)
14 forces[i] = force
15
16 # Calculate left forces
17 force = 0
18 for i in range(n - 1, -1, -1):
19 if dominoes[i] == 'L':
20 force = n # A large force imposed by L
21 elif dominoes[i] == 'R':
22 force = 0 # No force given by R
23 else:
24 force = max(force - 1, 0)
25 forces[i] -= force
26
27 # Determine the final state
28 result = []
29 for f in forces:
30 if f == 0:
31 result.append('.')
32 elif f > 0:
33 result.append('R')
34 else:
35 result.append('L')
36
37 return ''.join(result)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.
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.
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.
1import java.util.*;
2
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Push Dominoes is a common medium-level interview problem that tests simulation, string processing, and two-pointer reasoning. Variations of this problem have appeared in technical interviews at large tech companies.
The optimal approach uses a two-pointer or segment analysis technique to examine the forces between domino pushes. By evaluating patterns like R...L, L...R, R...R, and L...L, you can determine the final state in linear time without simulating each step.
While not strictly required, the force propagation method resembles dynamic programming by storing intermediate influence values from both directions. These values are combined to determine the final direction of each domino.
The problem mainly relies on string traversal and pointer tracking rather than complex data structures. Arrays or simple string manipulation are sufficient, while some implementations use auxiliary arrays to store left and right force values.
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.