Problem Description

You have n dominoes standing upright in a line. Initially, you push some dominoes either to the left or to the right simultaneously.

The dominoes follow these rules:

• Each second, a domino falling left pushes the domino immediately to its left
• Each second, a domino falling right pushes the domino immediately to its right
• When a vertical domino receives forces from both sides at the same time, it stays upright due to balanced forces
• A falling domino doesn't apply extra force to an already falling or fallen domino

You're given a string dominoes representing the initial state where:

• dominoes[i] = 'L' means the i-th domino was pushed to the left
• dominoes[i] = 'R' means the i-th domino was pushed to the right
• dominoes[i] = '.' means the i-th domino wasn't pushed

Your task is to return a string representing the final state after all dominoes have stopped moving.

For example, if you have ".L.R...LR..L..", the dominoes will propagate their falls over time. An R domino will cause dominoes to its right to fall right, an L domino will cause dominoes to its left to fall left, and when these forces meet at the same time, the domino stays upright.

The solution uses a multi-source BFS approach where all initially pushed dominoes serve as sources that propagate their forces outward simultaneously. It tracks the time each domino is first affected and the forces acting on it. If a domino receives only one force, it falls in that direction. If it receives opposite forces at the same moment, it remains upright.

Intuition

The key insight is to think of this problem as a wave propagation scenario. When dominoes are pushed, they create "waves" of force that spread outward over time. An R domino creates a rightward wave, and an L domino creates a leftward wave.

Consider what happens in real physics: if you push multiple dominoes simultaneously, their effects spread outward at the same speed. Each domino falls one unit of time after the previous one in the chain. This naturally suggests a BFS approach where we process dominoes layer by layer based on time.

Why BFS? Because we need to simulate the simultaneous propagation of forces. All initially pushed dominoes (the sources) start falling at time 0. Their immediate neighbors are affected at time 1, then those neighbors' neighbors at time 2, and so on. This is exactly what BFS does - it processes nodes level by level.

The critical observation is about collision handling: when two waves meet, we need to know if they arrive at the same time. If a rightward wave and a leftward wave reach the same domino at the exact same moment, the forces cancel out and the domino stays upright. If one wave arrives first, that domino falls in that direction and blocks the other wave.

This timing aspect is crucial. We can't just scan left-to-right or right-to-left because forces propagate simultaneously from multiple sources. We need to track:

1. When each domino is first affected (time[i])
2. What forces reach it at that moment (force[i])

By using a queue and processing dominoes in the order they're affected, we naturally simulate the simultaneous propagation of all forces. When we encounter a domino that's already been visited, we check if the new force arrives at the same time (creating a standoff) or later (in which case it's blocked).

This multi-source BFS elegantly handles all the complex interactions between multiple falling sequences, making what could be a complicated simulation into a clean, systematic traversal.

Learn more about Two Pointers and Dynamic Programming patterns.

Solution Approach

The solution implements a multi-source BFS where all initially pushed dominoes (L or R) serve as sources that propagate their forces outward simultaneously.

Data Structures:

• q: A deque (double-ended queue) to perform BFS traversal
• time[i]: An array tracking when the i-th domino is first affected by a force (-1 means not affected yet)
• force[i]: A dictionary of lists storing all force directions ('L' or 'R') acting on domino i at the same moment
• ans: The result array initialized with '.' for all positions

Algorithm Steps:

1. Initialization Phase:

   • Scan through the input string to find all initially pushed dominoes (L or R)
   • For each pushed domino at index i:
     • Add index i to the queue
     • Set time[i] = 0 (affected at time 0)
     • Add the force direction to force[i]

2. BFS Propagation Phase: While the queue is not empty:

   • Dequeue index i
   • If len(force[i]) == 1, the domino falls in direction f = force[i][0]
     • Set ans[i] = f
     • Calculate next domino index: j = i - 1 if f == 'L', else j = i + 1
     • If j is within bounds [0, n):
       • Case 1: If time[j] == -1 (not affected yet):
         • Enqueue j
         • Set time[j] = time[i] + 1
         • Append force f to force[j]
       • Case 2: If time[j] == time[i] + 1 (affected at the same next moment):
         • Append force f to force[j]
         • This creates a standoff if forces are opposite
   • If len(force[i]) == 2, the domino stays upright (balanced forces), so ans[i] remains '.'

3. Result Construction:

   • Join the ans array to form the final string

Key Insights:

• The BFS ensures we process dominoes in chronological order of when they're affected
• By checking time[j] == time[i] + 1, we detect when two waves meet at the same moment
• When force[j] contains two elements, it means opposing forces arrived simultaneously, keeping the domino upright
• The algorithm naturally handles complex scenarios like multiple force sources and wave collisions

Time Complexity: O(n) where n is the length of the string, as each domino is processed at most once Space Complexity: O(n) for the auxiliary data structures

Example Walkthrough

Let's trace through the example ".L.R...LR..L.." step by step.

Initial Setup:

• Input: ".L.R...LR..L.."
• Positions: 0 1 2 3 4 5 6 7 8 9 10 11 12 13
• Initially pushed dominoes are at indices: 1 (L), 3 (R), 7 (L), 8 (R), 11 (L)

Initialization Phase:

• Queue: [1, 3, 7, 8, 11]
• time = [-1, 0, -1, 0, -1, -1, -1, 0, 0, -1, -1, 0, -1, -1]
• force = {1: ['L'], 3: ['R'], 7: ['L'], 8: ['R'], 11: ['L']}
• ans = ['.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.']

BFS Propagation:

Processing index 1 (L):

• Single force 'L', so ans[1] = 'L'
• Next domino: j = 0 (to the left)
• time[0] = -1, so enqueue 0, set time[0] = 1, force[0] = ['L']
• Queue: [3, 7, 8, 11, 0]

Processing index 3 (R):

• Single force 'R', so ans[3] = 'R'
• Next domino: j = 4 (to the right)
• time[4] = -1, so enqueue 4, set time[4] = 1, force[4] = ['R']
• Queue: [7, 8, 11, 0, 4]

Processing index 7 (L):

• Single force 'L', so ans[7] = 'L'
• Next domino: j = 6 (to the left)
• time[6] = -1, so enqueue 6, set time[6] = 1, force[6] = ['L']
• Queue: [8, 11, 0, 4, 6]

Processing index 8 (R):

• Single force 'R', so ans[8] = 'R'
• Next domino: j = 9 (to the right)
• time[9] = -1, so enqueue 9, set time[9] = 1, force[9] = ['R']
• Queue: [11, 0, 4, 6, 9]

Processing index 11 (L):

• Single force 'L', so ans[11] = 'L'
• Next domino: j = 10 (to the left)
• time[10] = -1, so enqueue 10, set time[10] = 1, force[10] = ['L']
• Queue: [0, 4, 6, 9, 10]

Processing index 0 (L from index 1):

• Single force 'L', so ans[0] = 'L'
• Next domino: j = -1 (out of bounds), skip
• Queue: [4, 6, 9, 10]

Processing index 4 (R from index 3):

• Single force 'R', so ans[4] = 'R'
• Next domino: j = 5 (to the right)
• time[5] = -1, so enqueue 5, set time[5] = 2, force[5] = ['R']
• Queue: [6, 9, 10, 5]

Processing index 6 (L from index 7):

• Single force 'L', so ans[6] = 'L'
• Next domino: j = 5 (to the left)
• time[5] = 2 and time[6] + 1 = 2, so same moment!
• Append 'L' to force[5], now force[5] = ['R', 'L']
• Queue: [9, 10, 5]

Processing index 9 (R from index 8):

• Single force 'R', so ans[9] = 'R'
• Next domino: j = 10 (to the right)
• time[10] = 1 and time[9] + 1 = 2, different times, skip
• Queue: [10, 5]

Processing index 10 (L from index 11):

• Single force 'L', so ans[10] = 'L'
• Next domino: j = 9 (to the left)
• time[9] = 1 and time[10] + 1 = 2, different times, skip
• Queue: [5]

Processing index 5:

• force[5] = ['R', 'L'] (two forces), so domino stays upright
• ans[5] remains '.'
• Queue: []

Final Result:

• ans = ['L', 'L', '.', 'R', 'R', '.', 'L', 'L', 'R', 'R', 'L', 'L', '.', '.']
• Output: "LL.RR.LLRRLL.."

The key moment was at index 5, where forces from both directions arrived at time 2, creating a standoff and keeping that domino upright.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm uses BFS traversal where:

• Initial setup iterates through all n dominoes once to find non-'.' dominoes and add them to the queue: O(n)
• The while loop processes each position at most once. Each domino position can be added to the queue at most once (when time[j] == -1), and each position is dequeued at most once
• For each dequeued position, we perform constant time operations: checking force length, updating answer, and potentially adding one neighbor to the queue
• Total operations: O(n) for initialization + O(n) for BFS traversal = O(n)

Space Complexity: O(n)

The algorithm uses several data structures:

• time array of size n: O(n)
• force defaultdict that in worst case stores forces for all n positions (though each position stores at most 2 forces): O(n)
• ans array of size n: O(n)
• q deque that contains at most n elements: O(n)
• Total space: O(n) + O(n) + O(n) + O(n) = O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Handling Simultaneous Force Arrivals Correctly

The Pitfall: A common mistake is to process dominoes in the wrong order or not properly track when multiple forces reach the same domino simultaneously. If you process dominoes sequentially without considering timing, you might incorrectly apply one force before another when they should cancel out.

Example of Incorrect Approach:

# WRONG: Processing left-to-right then right-to-left separately
def pushDominoes_wrong(dominoes):
    result = list(dominoes)
    # First pass: process R forces
    for i in range(len(dominoes)):
        if result[i] == 'R' and i + 1 < len(result) and result[i + 1] == '.':
            result[i + 1] = 'R'
    # Second pass: process L forces
    for i in range(len(dominoes) - 1, -1, -1):
        if result[i] == 'L' and i - 1 >= 0 and result[i - 1] == '.':
            result[i - 1] = 'L'
    return ''.join(result)

This fails for input like "R.L" because it would produce "RRL" instead of the correct "R.L" (middle domino stays upright).

The Solution: Use BFS with proper time tracking to ensure forces that arrive simultaneously are processed together:

• Track the exact time each domino is first affected
• Only allow forces to be added if they arrive at the correct time
• Check time_reached[next_index] == current_time + 1 to identify simultaneous arrivals

2. Incorrectly Handling Already Falling Dominoes

The Pitfall: Attempting to add forces to dominoes that have already been processed or allowing a domino to change direction after it has started falling.

Example of Incorrect Logic:

# WRONG: Allowing dominoes to be re-queued multiple times
if 0 <= next_index < n:
    queue.append(next_index)  # Always adding without checking
    forces_at_position[next_index].append(force_direction)

The Solution: Only process each domino once by:

• Using the time_reached array to ensure a domino is only added to the queue when first affected
• Not allowing new forces to affect a domino after its initial time window has passed

3. Off-by-One Errors in Boundary Checking

The Pitfall: Forgetting to check array boundaries when calculating the next domino position, leading to index out of bounds errors.

Example of Incorrect Code:

# WRONG: No boundary check
next_index = current_index - 1 if force_direction == 'L' else current_index + 1
queue.append(next_index)  # Could be -1 or n!

The Solution: Always validate the next index before using it:

if 0 <= next_index < n:
    # Safe to process next_index

4. Misunderstanding Force Cancellation

The Pitfall: Assuming that any two forces cancel out, regardless of their directions or thinking that a domino with two forces should fall in some combined direction.

The Correct Understanding:

• Only opposite forces ('L' and 'R') arriving simultaneously cause a domino to remain upright
• If the same force arrives twice (e.g., two 'R' forces), it's still just one directional force
• The code correctly handles this by checking len(forces_at_position[current_index]) == 1 to determine if the domino falls

5. Not Initializing the Result Array Properly

The Pitfall: Starting with the input string as the result and modifying it in place, which can lead to confusion about which dominoes have been processed.

Example of Problematic Approach:

# RISKY: Using input as starting point
result = list(dominoes)  # Contains 'L', 'R', and '.'

The Solution: Initialize the result array with all dots (standing dominoes) and only update positions as they're processed:

result = ['.'] * n  # Clear initial state

This ensures that any domino not affected by forces remains standing (.) in the final result.