Problem Statement in English

You’re given a string dominoes representing the state of dominoes, where each character can be:

  • R: a domino that is falling to the right
  • L: a domino that is falling to the left
  • .: a domino that is upright and not falling

Your task is to simulate the falling dominoes and return the final state of the dominoes after all possible falls have occurred.

Approach

This problem can be solved using a multi-source breadth-first search (BFS) approach. The idea is to treat each domino as a node and simulate the falling process by propagating the effects of each falling domino to its neighbors.

You also need to handle cases where a domino on the right falls on a domino which is standing upright, and has a domino on the left falling towards it. In such cases, the dominoes will fall in a way that they meet in the middle, if the time at which the domino on the left falls is equal to the time at which the domino on the right falls.

So you need to keep track of time.

Solution in Python

class Solution:
    def pushDominoes(self, dominoes: str) -> str:
        res = list(dominoes)
        l = len(res)
        q = deque()
        time = {}

        for i, dir in enumerate(res):
            if dir != ".":
                new_dir = i + 1 if dir == "R" else i - 1
                q.append((new_dir, dir, 1))
                time[i] = 0

        while q:
            d, dir, t = q.popleft()

            if (not (0 <= d < l)) or res[d] != ".":
                continue

            if d-1 >= 0 and res[d-1] == "R" and d+1 < l and res[d+1] == "L" and time[d-1] == time[d+1]:
                continue

            res[d] = dir
            time[d] = t

            nd = d + 1 if dir == "R" else d - 1
            if 0 <= nd < l and res[nd] == ".":
                q.append((nd, dir, t + 1))

        return "".join(res)

Complexity

  • Time: $O(n)$
    Since we process each domino at most once, where $n$ is the length of the dominoes string.

  • Space: $O(n)$
    Since we use a queue to store the dominoes and a dictionary to keep track of the time at which each domino falls, where $n$ is the length of the dominoes string.

And we are done.