Pushing Dominoes (LeetCode/LintCode)

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.

Given a string “S” representing the initial state. S[i] = 'L', if the i-th domino has been pushed to the left; S[i] = 'R', if the i-th domino has been pushed to the right; S[i] = '.', if the i-th domino has not been pushed.

Return a string representing the final state.

Photo by Adrien Olichon on Unsplash

Thinking Process

Suppose there are Right falling domino and Left falling domino equidistant to a position with a non-falling domino at i (let’s call it “D”)(in between these are also non-falling dominoes), D will not fall. One domino to the left of D, it will fall to the right, and one domino to the right of D, it will fall to the left.

Clearly the relative distance from current position of a standing domino and adjacent dominoes that are set to fall will decide whether the end state of the current standing domino.

Before

After — NF (Not Fall), F (Fall)

How to Solve

Hence, at any position, if it’s a domino that is standing, we will compare the distance to the nearest left or right falling dominoes. The nearest falling domino will determine the fate of the standing domino.

We can use a left and rightvariables, where left[i] and right[i]stores the distance to the nearest falling dominoes. There will be a corner case, where for a position, there is no falling variables to the left or right. In this case, the variables will store ∞.

Filling the Variables

Then as we traverse across iwe have three choices to fill up the variables. To illustrate, for leftvariable:

A) If left[i] == “L”, set left[i] = 0, since the nearest “L” is at the same position to fill;

B) If left[i]== “.”, set left[i] = left[i-1] + 1; and

C) If left[i] == “R”, don’t set left[i] i.e. it will remains as ∞.

Note: There is a two corner cases for step B), because i could be at position zero and left[i-1] is undefined. In this case, don’t set and leave left[i=0] as ∞. Or, left[i-1] is ∞, meaning no falling “L” from the left, then again leave left[i] as ∞.

I will leave the exercise to fill right[i] to the reader.

Code Spoilers (In Python)— Don’t scroll if you are still figuring out

import math
class Solution:
    """
    @param dominoes: a string
    @return: a string representing the final state
    """
    def pushDominoes(self, dominoes):
        length = len(dominoes)
        left = [math.inf for _ in range(length)]
        right = [math.inf for _ in range(length)]
        res =  []
        
        for i in range(length):
            
            li = length - i - 1
            
            if dominoes[li] == "L":
                left[li] = 0
            elif dominoes[li] == ".":
                if li != length-1:
                    if left[li+1] != math.inf: #DP portion
                        left[li] = left[li+1] + 1          
                        
            if dominoes[i] == "R":
                right[i] = 0
            elif dominoes[i] == ".":
                if i != 0:
                    if right[i-1] != math.inf: #DP portion
                        right[i] = right[i-1] + 1
                    
        for i in range(length):
            if right[i] < left[i]:
                res.append("R")
            elif right[i] > left[i]:
                res.append("L")
            else:
                res.append(".")
        return "".join(res)