{x}
blog image

Push Dominoes

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 '.'.

Solution Explanation:

This problem simulates the falling of dominoes. The solution uses a breadth-first search (BFS) approach to model the dominoes' behavior over time.

Algorithm:

  1. Initialization:

    • Create a time array to track when each domino falls. Initialize all values to -1 (not fallen).
    • Create a force array (or equivalent data structure) to store the forces acting on each domino. Each element will hold a list of forces ('L' or 'R').
    • Create a queue q to store the indices of the initially pushed dominoes.

  2. BFS:

    • Iterate while the queue is not empty.
    • Dequeue an index i from the queue.
    • If force[i] has only one element, this domino is pushed in one direction.
      • Assign the force direction to ans[i].
      • Find the adjacent domino j depending on the direction ('L' or 'R').
      • If j is within bounds:
        • If time[j] is -1 (not yet fallen), add j to the queue, update time[j], and add the force to force[j].
        • If time[j] is equal to time[i] + 1, this means the domino will be pushed by multiple dominoes simultaneously, so add the force to force[j].

  3. Result:

    • The ans array now contains the final state of the dominoes. Join the array elements into a string and return the result.

Time Complexity: O(N), where N is the length of the dominoes string. Each domino is processed at most once (or more precisely, its state is updated at most a constant number of times).

Space Complexity: O(N), primarily due to the time and force arrays, and queue.

Code Explanation (Python):

The Python solution demonstrates the described algorithm efficiently using a deque (for fast queue operations) and a defaultdict (for convenient handling of forces). Let's breakdown the key parts:

from collections import deque, defaultdict
 
class Solution:
    def pushDominoes(self, dominoes: str) -> str:
        n = len(dominoes)
        q = deque()
        time = [-1] * n
        force = defaultdict(list)  # Use defaultdict to avoid KeyError
        # ... (rest of the code as in the previous response)
  • defaultdict(list): This creates a dictionary where each key (domino index) defaults to an empty list if it doesn't exist. This simplifies adding forces without explicit checks.
        for i, f in enumerate(dominoes):
            if f != '.':
                q.append(i)
                time[i] = 0
                force[i].append(f)

This part iterates through the initial dominoes, adding those that are initially pushed ('L' or 'R') to the queue and initializing their time and force.

        while q:
            i = q.popleft()
            if len(force[i]) == 1:  # Check for single force
                # ... (rest of the BFS logic)

The main BFS loop handles dominoes one by one, processing only those with a single, unambiguous force.

The remaining code implements the BFS logic as described in the algorithm, correctly handling the propagation of forces and updating domino states.

Code Explanation (Other Languages):

The code in other languages (Java, C++, Go, TypeScript) follows the same algorithmic principles, with minor syntactic differences reflecting the respective language features. The core data structures (queue, time array, and force representation) and the BFS logic are consistently applied. For instance, Java uses ArrayDeque for the queue and ArrayList for forces, while C++ uses queue and vector<string>, and Go uses slices for similar purposes. TypeScript utilizes its array and map capabilities to achieve the same functionality.