Push Dominoes

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.

  Note: By the end of this loop, forces array will have either 0 or positive numbers, after computing net forces if the result remains positive, that means it is going to be 'R' domino.

• 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;
        // going from left to right, towards right, meaning R falls on neighbour dominoes
        for(int i=0; i<n; i++) {
            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.