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.
1#include <queue>
2#include <string>
3
4class Solution {
public:
std::string pushDominoes(std::string dominoes) {
int n = dominoes.size();
std::string result = dominoes;
std::queue<int> queue;
for (int i = 0; i < n; ++i) {
if (dominoes[i] != '.') {
queue.push(i);
}
}
while (!queue.empty()) {
int i = queue.front(); queue.pop();
char d = result[i];
if (d == 'L' && i > 0 && result[i - 1] == '.') {
result[i - 1] = 'L';
queue.push(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.push(i + 1);
}
}
return result;
}
};The C++ code provided follows a similar approach to handle simulations using a queue. It applies forces while maintaining a 'to-do' list of dominoes but with STL constructs.