Arrays - Push Dominoes

There are n dominoes in a line, and we place each domino vertically upright. In the beginning, we simultaneously push some of the dominoes either to the left or to the right.

After each second, each domino that is falling to the left pushes the adjacent domino on the left. Similarly, the dominoes falling to the right push their adjacent dominoes standing on the right.

When a vertical domino has dominoes falling on it from both sides, it stays still due to the balance of the forces.

For the purposes of this question, we will consider that a falling domino expends no additional force to a falling or already fallen domino.

You are given a string dominoes representing the initial state where:

dominoes[i] = 'L', if the i^th domino has been pushed to the left,
dominoes[i] = 'R', if the i^th domino has been pushed to the right, and
dominoes[i] = '.', if the i^th domino has not been pushed.

Return a string representing the final state.

Input: dominoes = "RR.L"
Output: "RR.L"
Explanation: The first domino expends no additional force on the second domino.

Input: dominoes = ".L.R...LR..L.."
Output: "LL.RR.LLRRLL.."
Explanation: below picture representing the input string
Example 2a

below picture representing the output after Dominoes pushed to left and right sides.
Example 2b

Constraints:

n == dominoes.length
1 <= n <= 10⁵
dominoes[i] is either 'L', 'R', or '.'.

Solution 1 - Using two pass technique, calculate the net force at each position

Let's understand one thing from the problem, if the domino at position i is 'L' it falls on to the neighbouring dominoes on left side, if it is 'R' then it falls on to the neighbouring dominoes on right side, and if it is '.' then it is not falling on either side.

At each second, the domino is falling on left side is pushing other vertical dominoes towards left and the domino falling on right side is pushing other vertical dominoes towards right.
If there is a vertical domino in between a 'L' and 'R' that stays vertical. This is an important piece of information for the below approach, if there is one vertical domino between L and R, for example R.L then it stays as is. But, if there are odd number of vertical dominoes, for example R...L, centered domino stays vertical, R will fall to the right, and L will fall to the left.

In this approach, we will use a temporary array to calculate forces at each index, i.e. one time towards right direction, compute the affect of domonies falling to right side 'R', and second time towards left direction, compute the affect of dominoes falling to left side 'R', this will give us the net affect of both L and R are falling at the same time.

implementation details:

We will first initialize a temporary to store the forces, call it forces, and another variable force to keep track of net force at current index.
Then, will loop through each domino from left to right and do the following:
- If the domino is 'R' then, set force to n (the length of 'dominoes' input string, because the maximum number of domonies that a R can fall on are n-1 other dominoes if the current domino is R).
- If the domino is 'L' then, set force to 0 (to break that force as this would fall onto left side).
- If the domino is '.' then, set force to MAX(force-1, 0) (reason for this is we want to see whether force continues to decrement, that is if R continues to fall without any 'L' in between).
- Update forces array at current index with the force value computed from above 3 conditions.
Now, reset force = 0 and loop through each domino from right to left and do the following:
- If the domino is 'L' then, set force to n.
- If the domino is 'R' then, set force to 0.
- If the domino is '.' then, set force to MAX(force-1, 0) (reason for this is we want to see whether force continues to decrement, that is if R continues to fall without any 'L' in between).
- Update forces array at current index with the -force value computed from above 3 conditions. The reason we are subtracting with force is to get the net force value.
Finally, loop through forces array, and if the value is less than 0, then that is a left domino 'L', if the value is greater than 0, then that is a right domino and if the value is 0, then it is a vertical domino ..

Example:

Consider an example with dominoes = ".L.R...LR..L..".

After first pass from left to right, forces array will look like this, [0, 0, 0, 14, 13, 12, 11, 0, 14, 13, 12, 0, 0, 0].
After second pass from right to left, forces array will look like this, [-13, -14, 0, 14, 2, 0, -2, -14, 14, 1, -1, -14, 0, 0].
So, the final state of dominoes will be, LL.RR.LLRRLL...

public class PushDominoes { static String pushDominoes(String dominoes) { char[] dominoesArray = dominoes.toCharArray(); int n = dominoesArray.length; int[] forces = new int[n]; int force = 0; for(int i=0; i<n; i++) { // going from left to right, towards right, meaning R falls on neighbour dominoes if(dominoesArray[i] == 'R') { force = n; } else if(dominoesArray[i] == 'L') { force = 0; } else { force = Math.max(force-1, 0); } forces[i] += force; } force = 0; for(int i=n-1; i>=0; i--) { if(dominoesArray[i] == 'L') { force = n; } else if (dominoesArray[i] == 'R') { force = 0; } else { force = Math.max(force-1, 0); } forces[i] -= force; } StringBuilder sb = new StringBuilder(); for(int i=0;i<n; i++) { if(forces[i] <0) { sb.append('L'); } else if (forces[i]>0) { sb.append('R'); } else { sb.append('.'); } } return sb.toString(); } public static void main(String[] args) { System.out.println(pushDominoes(".L.R...LR..L..")); } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the length of dominoes input string.
Space complexity: O(n), since we are using a temporary array to store the net forces.

Above implementations source code can be found at GitHub link for Java code

Constraints:

Contents

implementation details:

Example:

Complexity Analysis: