[Array]LC 838. Push Dominoes

Push Dominoes - LeetCode

Goal

• 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.
• Return a string representing the final state

Input: dominoes = ".L.R...LR..L.."
Output: "LL.RR.LLRRLL.."

Strategy

• traverse the array 2 times, first from L → R, second R → L
• set up an array to store the net force, because we need to consider forces coming from both L & R
• for example we go from L → R, when we see L, the force is 0, if we see R, the force is n (length of the string), because it pushes the consecutive block; when neither of L & R, we use max(n-1, 0) to check whether we carried over the previous force
• we add the current force to the corresponding index in the net force array
• according to the values in the net force array, we decide the final directions

Complexity

• Time: O(N) as we traverse the array 2 times
• Space: O(N) as we used an extra array

Highlight

• The idea of Net Force,
• Traverse the array from both directions, which is also the core concept of the collect water problem

Code

class Solution:
    def pushDominoes(self, dominoes: str) -> str:
        
        arr = list(dominoes)
        
        res = []
        
        n = len(dominoes)
        
        forces = [0 for i in range(n)]
        force = 0
        for i in range(n):
            if dominoes[i] == 'R':
                force = n
            elif dominoes[i] == 'L':
                force = 0
            else:
                force = max(force-1, 0)
            forces[i] +=force
        
        force = 0
        
        for i in range(n-1,-1,-1):
            if dominoes[i] == 'L':
                force = n
            elif dominoes[i] == 'R':
                force = 0
            else:
                force = max(force-1, 0)
            forces[i] -=force
        
        for f in forces:
            if f > 0:
                res.append('R')
            elif f < 0:
                res.append('L')
            else:
                res.append('.')
            
        return ''.join(res)