Sponsored
Sponsored
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.
1function pushDominoes(dominoes) {
2 const n = dominoes.length;
3 const forces = Array(n).fill(0);
4
5 // Calculate right forces
6 let force = 0;
7 for (let i = 0; i < n; i++) {
8 if (dominoes[i] === 'R') {
9 force = n;
10 } else if (dominoes[i] === 'L') {
11 force = 0;
12 } else {
13 force = Math.max(force - 1, 0);
14 }
15 forces[i] = force;
16 }
17
18 // Calculate left forces
19 force = 0;
20 for (let i = n - 1; i >= 0; i--) {
21 if (dominoes[i] === 'L') {
22 force = n;
23 } else if (dominoes[i] === 'R') {
24 force = 0;
25 } else {
26 force = Math.max(force - 1, 0);
27 }
28 forces[i] -= force;
29 }
30
31 // Determine the final state
32 return forces.map(f => f === 0 ? '.' : (f > 0 ? 'R' : 'L')).join('');
33}In this JavaScript code, the same two-pass technique is applied to determine the resultant forces on the dominoes. This appends the final states into an array that converts to a string to output.
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
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.