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.
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.
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.