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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
public string PushDominoes(string dominoes) {
int n = dominoes.Length;
char[] result = dominoes.ToCharArray();
Queue<int> queue = new Queue<int>();
for (int i = 0; i < n; ++i) {
if (dominoes[i] != '.') {
queue.Enqueue(i);
}
}
while (queue.Count > 0) {
int i = queue.Dequeue();
char d = result[i];
if (d == 'L' && i > 0 && result[i - 1] == '.') {
result[i - 1] = 'L';
queue.Enqueue(i - 1);
}
if (d == 'R' && i + 1 < n && result[i + 1] == '.') {
if (i + 2 < n && result[i + 2] == 'L') {
continue;
}
result[i + 1] = 'R';
queue.Enqueue(i + 1);
}
}
return new string(result);
}
}This C# implementation uses a queue to simulate the chain reaction effect of falling dominoes, mirroring the logical flow as seen in the other implementations.