Problem of The Day: Push Dominoes

Problem Statement

leetcode problem link

Intuition

To simulate how dominoes fall over time, we need to consider the influence of each ‘R’ (right push) and ‘L’ (left push) on the dominoes around them. A domino gets pushed by its nearest force unless equal forces cancel out. Therefore, tracking the distance from the closest ‘R’ and ‘L’ is crucial to determining the final state of each domino.

Approach

1. Create three lists: right, left, and res, initialized with the input string.
2. Traverse from left to right to simulate rightward forces:
   • Whenever an ‘R’ is encountered, start counting distance (force) from that point.
   • Update the right list with the distance to the nearest ‘R’ for each domino.
3. Traverse from right to left to simulate leftward forces:
   • Whenever an ‘L’ is encountered, start counting distance (force) from that point.
   • Update the left list with the distance to the nearest ‘L’ for each domino.
4. Iterate over each domino:
   • If the domino is ‘.’, compare the left and right forces:
     • If they are equal, do nothing (forces cancel).
     • If left is stronger, set to ‘L’.
     • If right is stronger, set to ‘R’.
5. Return the final state as a string.

Complexity

• Time complexity:
  \(O(n)\)
  Each domino is visited a constant number of times.

• Space complexity:
  \(O(n)\)
  Additional space is used for right, left, and res arrays.

Code

class Solution:
    def pushDominoes(self, dominoes: str) -> str:
        right = list(dominoes)
        left = list(dominoes)
        res = list(dominoes)
        N = len(dominoes)
        force = 0
        curr = ''
        for i in range(N):
            if dominoes[i] == 'R':
                curr = 'R'
                force = 0
            elif dominoes[i] == 'L':
                curr = 'L'
                force = 0
            if curr == 'R':
                right[i] = force
                force += 1

        curr = ''
        for i in range(N - 1, -1, -1):
            if dominoes[i] == 'R':
                curr = 'R'
                force = 0
            elif dominoes[i] == 'L':
                curr = 'L'
                force = 0
            if curr == 'L':
                left[i] = force
                force += 1

        for i in range(N):
            if dominoes[i] == '.':
                if left[i] == right[i]:
                    continue
                l_val = float('inf') if str(left[i]) in 'RL.' else left[i]
                r_val = float('inf') if str(right[i]) in 'RL.' else right[i]
                if l_val < r_val:
                    res[i] = 'L'
                else:

Editorial

Approach #1: Adjacent Symbols [Accepted]

class Solution(object):
    def pushDominoes(self, dominoes):
        symbols = [(i, x) for i, x in enumerate(dominoes) if x != '.']
        symbols = [(-1, 'L')] + symbols + [(len(dominoes), 'R')]

        ans = list(dominoes)
        for (i, x), (j, y) in zip(symbols, symbols[1:]):
            if x == y:
                for k in xrange(i+1, j):
                    ans[k] = x
            elif x > y: #RL
                for k in xrange(i+1, j):
                    ans[k] = '.LR'[cmp(k-i, j-k)]

        return "".join(ans)

Approach #2: Calculate Force [Accepted]

class Solution(object):
    def pushDominoes(self, dominoes):
        N = len(dominoes)
        force = [0] * N

        # Populate forces going from left to right
        f = 0
        for i in xrange(N):
            if dominoes[i] == 'R': f = N
            elif dominoes[i] == 'L': f = 0
            else: f = max(f-1, 0)
            force[i] += f

        # Populate forces going from right to left
        f = 0
        for i in xrange(N-1, -1, -1):
            if dominoes[i] == 'L': f = N
            elif dominoes[i] == 'R': f = 0
            else: f = max(f-1, 0)
            force[i] -= f

        return "".join('.' if f==0 else 'R' if f > 0 else 'L'
                       for f in force)