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.
1#include <string.h>
2#include <stdlib.h>
3
4char* pushDominoes(char* dominoes) {
5 int n = strlen(dominoes);
6 int* forces = (int*)calloc(n, sizeof(int));
7 char* result = (char*)malloc((n + 1) * sizeof(char));
8 int i, force = 0;
9
10 // Calculate right forces
11 for (i = 0; i < n; ++i) {
12 if (dominoes[i] == 'R') {
13 force = n; // A large force imposed by R
14 } else if (dominoes[i] == 'L') {
15 force = 0; // No force given by L
16 } else {
17 force = force > 0 ? force - 1 : 0;
18 }
19 forces[i] = force;
20 }
21
22 // Calculate left forces
23 for (i = n - 1; i >= 0; --i) {
24 if (dominoes[i] == 'L') {
25 force = n; // A large force imposed by L
26 } else if (dominoes[i] == 'R') {
27 force = 0; // No force given by R
28 } else {
29 force = force > 0 ? force - 1 : 0;
30 }
31 forces[i] -= force;
32 }
33
34 // Determine the final state
35 for (i = 0; i < n; ++i) {
36 if (forces[i] == 0) {
37 result[i] = '.';
38 } else if (forces[i] > 0) {
39 result[i] = 'R';
40 } else {
41 result[i] = 'L';
42 }
43 }
44 result[n] = '\0'; // Null-terminate the string
45
46 free(forces);
47 return result;
48}The C implementation employs the same logic as the Python solution using two passes to cumulatively calculate forces. Forces are stored in an integer array and used to determine the final position of each domino.
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.