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 '.'.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.
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.
C++
C#
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.
| 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. |
Push Dominoes - Leetcode 838 - Python • NeetCode • 23,343 views views
Watch 9 more video solutions →Practice Push Dominoes with our built-in code editor and test cases.
Practice on FleetCode