Leetcode 838 Push Dominos

Problem description

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 ith domino has been pushed to the left,
• dominoes[i] = 'R', if the ith domino has been pushed to the right, and
• dominoes[i] = '.', if the ith domino has not been pushed. Return a string representing the final state.

Example 1:

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

Example 2:

• Input: dominoes = “.L.R…LR..L..”
• Output: “LL.RR.LLRRLL..”

Constraints:

• n == dominoes.length
• 1 <= n <= 105 dominoes[i] is either ‘L’, ‘R’, or ‘.’.

Problem Solving Process (Solution B)

During the coding interview, I gave a solution to use two pointer to determine the domino with or without force. Left pointer always points to the domino without force and right pointer points to the one with force. But this method need to consider the direction force. To solve this problem we can treat L and R as emitting forces that spread across the row.

Here is how we can solve it.

1. Create forces list to store the force strongness when iterator the dominos. The initial values are all 0.

2. From left to right pass

• We calculate the “rightward force” from R’s. When we see:

  • 'R': set strong force

  • 'L': reset force to zero

  • '.': force decreases by 1 each step since the force attenuates during transmission.

1. From right to left pass

• Same idea, but for L’s. This gives us “leftward force”.

1. Compare the forces

• At each position:

  • stronger right force: 'R'

  • stronger left force: 'L'

  • equal force: '.'

Code implementation

def pushDominoes(dominoes):
    n = len(dominoes)
    forces = [0]*n
    force = 0
    res = []
    
    # From left to right pass
    for i in range(n):
        if dominoes[i] == 'R':
            force = n
        elif dominoes[i] == 'L':
            force = 0
        else:
            force = max(force - 1, 0) #Force attenuation
        forces[i] += force
    
    # From right to left pass
    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

        # Compare force
    for force in forces:
        if force > 0:
            res.append('R')
        elif force < 0:
            res.append('L')
        else:
            res.append('.')
    return ''.join(res)

Complexity Analysis

• Time complexity: O(n). We used three for loop for n size string and list. O(3n) = O(n)

• Space complexity: O(n). Since we used one extra data structure forces and res. The complexity is O(2n) = O(n)