838: Push Dominoes

Difficulty: Medium

Topics: Two Pointers, Simulation, BFS

Companies: Google, Amazon, Microsoft

Pro Tip: This problem requires understanding force propagation in both directions. The optimal solution runs in O(n) time with O(n) space.

Problem Statement

There are n dominoes in a line, and we place each domino vertically upright. We push some dominoes either left ('L') or right ('R'), while others remain standing ('.'). Return the final state after all forces propagate.

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

Problem Link: View on LeetCode ↗

Approach 1: Force Propagation (Optimal)

Calculate net forces acting on each domino by traversing left-to-right (for 'R' forces) and right-to-left (for 'L' forces).

Algorithm Steps

Initialize a force array with zeros
Left-to-right pass: Calculate rightward forces (decreasing by 1 each step)
Right-to-left pass: Calculate leftward forces (decreasing by 1 each step)
Determine final state based on net force at each position

Complexity Analysis

Time Complexity	Space Complexity
O(n)	O(n)

Force Propagation Solution

class Solution {
public:
    string pushDominoes(string dominoes) {
        int n = dominoes.size();
        vector<int> forces(n, 0);
        
        // Rightward force propagation
        int force = 0;
        for (int i = 0; i < n; ++i) {
            if (dominoes[i] == 'R') force = n;
            else if (dominoes[i] == 'L') force = 0;
            else force = max(force - 1, 0);
            forces[i] += force;
        }
        
        // Leftward force propagation
        force = 0;
        for (int i = n-1; i >= 0; --i) {
            if (dominoes[i] == 'L') force = n;
            else if (dominoes[i] == 'R') force = 0;
            else force = max(force - 1, 0);
            forces[i] -= force;
        }
        
        // Build final result
        string result;
        for (int f : forces) {
            result += f > 0 ? 'R' : f < 0 ? 'L' : '.';
        }
        return result;
    }
};

class Solution {
    public String pushDominoes(String dominoes) {
        int n = dominoes.length();
        int[] forces = new int[n];
        
        // Rightward force
        int force = 0;
        for (int i = 0; i < n; ++i) {
            if (dominoes.charAt(i) == 'R') force = n;
            else if (dominoes.charAt(i) == 'L') force = 0;
            else force = Math.max(force - 1, 0);
            forces[i] += force;
        }
        
        // Leftward force
        force = 0;
        for (int i = n-1; i >= 0; --i) {
            if (dominoes.charAt(i) == 'L') force = n;
            else if (dominoes.charAt(i) == 'R') force = 0;
            else force = Math.max(force - 1, 0);
            forces[i] -= force;
        }
        
        // Build result
        StringBuilder sb = new StringBuilder();
        for (int f : forces) {
            sb.append(f > 0 ? 'R' : f < 0 ? 'L' : '.');
        }
        return sb.toString();
    }
}

class Solution:
    def pushDominoes(self, dominoes: str) -> str:
        n = len(dominoes)
        forces = [0] * n
        
        # Rightward force
        force = 0
        for i in range(n):
            if dominoes[i] == 'R':
                force = n
            elif dominoes[i] == 'L':
                force = 0
            else:
                force = max(force - 1, 0)
            forces[i] += force
        
        # Leftward force
        force = 0
        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
        
        # Build result
        result = []
        for f in forces:
            if f > 0:
                result.append('R')
            elif f < 0:
                result.append('L')
            else:
                result.append('.')
        return ''.join(result)

Implementation Note: The force propagation approach is elegant because it processes the dominoes in two passes (left-to-right and right-to-left), then combines the results. This avoids the need for complex simulation while maintaining optimal time complexity.

Approach 2: BFS Simulation

Simulate the domino effect using BFS to process forces level by level (second by second).

Algorithm Steps

Initialize a queue with all initially pushed dominoes
Process dominoes level by level, tracking time of impact
For each domino, push adjacent dominoes if not already falling
Handle collisions where forces meet

Complexity Analysis

Time Complexity	Space Complexity
O(n)	O(n)

BFS Simulation Solution

class Solution {
public:
    string pushDominoes(string dominoes) {
        int n = dominoes.size();
        queue<int> q;
        vector<int> time(n, -1);
        vector<char> force(n, '.');
        
        // Initialize queue with pushed dominoes
        for (int i = 0; i < n; ++i) {
            if (dominoes[i] != '.') {
                q.push(i);
                time[i] = 0;
                force[i] = dominoes[i];
            }
        }
        
        // Process dominoes level by level
        while (!q.empty()) {
            int i = q.front();
            q.pop();
            
            if (force[i] == 'L' && i > 0) {
                if (time[i-1] == -1) {
                    time[i-1] = time[i] + 1;
                    force[i-1] = 'L';
                    q.push(i-1);
                } else if (time[i-1] == time[i] + 1) {
                    force[i-1] = '.';
                }
            } else if (force[i] == 'R' && i < n-1) {
                if (time[i+1] == -1) {
                    time[i+1] = time[i] + 1;
                    force[i+1] = 'R';
                    q.push(i+1);
                } else if (time[i+1] == time[i] + 1) {
                    force[i+1] = '.';
                }
            }
        }
        
        return string(force.begin(), force.end());
    }
};

class Solution {
    public String pushDominoes(String dominoes) {
        int n = dominoes.length();
        Queue<Integer> q = new LinkedList<>();
        int[] time = new int[n];
        char[] force = new char[n];
        Arrays.fill(time, -1);
        Arrays.fill(force, '.');
        
        // Initialize queue
        for (int i = 0; i < n; i++) {
            if (dominoes.charAt(i) != '.') {
                q.offer(i);
                time[i] = 0;
                force[i] = dominoes.charAt(i);
            }
        }
        
        // Process dominoes
        while (!q.isEmpty()) {
            int i = q.poll();
            if (force[i] == 'L' && i > 0) {
                if (time[i-1] == -1) {
                    time[i-1] = time[i] + 1;
                    force[i-1] = 'L';
                    q.offer(i-1);
                } else if (time[i-1] == time[i] + 1) {
                    force[i-1] = '.';
                }
            } else if (force[i] == 'R' && i < n-1) {
                if (time[i+1] == -1) {
                    time[i+1] = time[i] + 1;
                    force[i+1] = 'R';
                    q.offer(i+1);
                } else if (time[i+1] == time[i] + 1) {
                    force[i+1] = '.';
                }
            }
        }
        
        return new String(force);
    }
}

class Solution:
    def pushDominoes(self, dominoes: str) -> str:
        n = len(dominoes)
        q = collections.deque()
        time = [-1] * n
        force = ['.'] * n
        
        # Initialize queue
        for i in range(n):
            if dominoes[i] != '.':
                q.append(i)
                time[i] = 0
                force[i] = dominoes[i]
        
        # Process dominoes
        while q:
            i = q.popleft()
            if force[i] == 'L' and i > 0:
                if time[i-1] == -1:
                    time[i-1] = time[i] + 1
                    force[i-1] = 'L'
                    q.append(i-1)
                elif time[i-1] == time[i] + 1:
                    force[i-1] = '.'
            elif force[i] == 'R' and i < n-1:
                if time[i+1] == -1:
                    time[i+1] = time[i] + 1
                    force[i+1] = 'R'
                    q.append(i+1)
                elif time[i+1] == time[i] + 1:
                    force[i+1] = '.'
        
        return ''.join(force)

When to Use BFS: The BFS approach is particularly useful when you need to simulate the domino effect step-by-step. It's more intuitive for understanding the propagation process but has the same time complexity as the force propagation method.

Comparison of Approaches

Approach	Time Complexity	Space Complexity	When to Use	Pros	Cons
Force Propagation	O(n)	O(n)	Optimal solution, clean implementation	Elegant two-pass solution, easy to understand	Less intuitive than simulation
BFS Simulation	O(n)	O(n)	When simulation is preferred	More intuitive, models physical process	Slightly more complex implementation

Interview Tip: While both approaches are valid, interviewers often appreciate candidates who can explain multiple solutions and discuss their trade-offs. The force propagation method is usually preferred for its elegance.

Edge Cases and Special Considerations

When implementing solutions for this problem, it's crucial to consider various edge cases that might affect the correctness of your code:

1. All Dominoes Standing

Input: "....."
Output: "....."
Explanation: No forces are applied, all dominoes remain standing.

2. All Dominoes Pushed Right

Input: "RRRRR"
Output: "RRRRR"
Explanation: All dominoes are already falling to the right.

3. All Dominoes Pushed Left

Input: "LLLLL"
Output: "LLLLL"
Explanation: All dominoes are already falling to the left.

4. Alternating Forces

Input: "R.L.R"
Output: "R.L.R"
Explanation: Forces cancel each other in the middle.

5. Complex Force Interactions

Input: ".L.R...LR..L.."
Output: "LL.RR.LLRRLL.."
Explanation: Demonstrates multiple force interactions.

Important: Always test your solution with these edge cases to ensure correctness. The examples above demonstrate how subtle force interactions can affect your results.

Visualization

The steps below demonstrates how forces propagate through the dominoes:

Initial state: .L.R...LR..L..
After 1 second: LL.RR.LLRRLL..
Final state: LL.RR.LLRRLL..

Notice how forces cancel each other when they meet at the same time.

Frequently Asked Questions

1. Why does the force propagation approach work?

It calculates net forces by considering both left and right influences separately then combining them, similar to how physical forces interact. The rightward pass captures all 'R' forces diminishing over distance, while the leftward pass does the same for 'L' forces.

2. How does the BFS approach handle collisions?

When two forces meet at the same time (same BFS level), the domino remains upright ('.') due to balanced forces. The BFS naturally processes all dominoes at each time step before moving to the next step.

3. What's the intuition behind the force values decreasing by 1?

It represents how force diminishes with distance from the original push (like real physics). Each domino further from the initial push receives less force, captured by decrementing the force value by 1 for each position away.

4. Can this be solved with constant space?

No, we need O(n) space to track intermediate states or forces. Both approaches require additional storage - the force array in the first approach and the queue/time arrays in the BFS approach.

5. How would you handle circular domino arrangements?

This problem assumes linear arrangement. Circular would require modulo arithmetic on indices and special handling for forces that wrap around. The force propagation approach would need to be adjusted to account for circular dependencies.

6. What's the worst-case scenario for BFS?

When dominoes alternate (R.L.R.L), requiring O(n) levels. However, since each domino is processed exactly once, the time complexity remains O(n).

7. Why is the force initialized to 'n'?

It ensures the force can propagate the maximum possible distance (n-1 steps). This guarantees the force will reach all dominoes in the direction it's propagating, decreasing by 1 at each step.

8. How does the solution handle consecutive 'R's?

Each 'R' resets the force to maximum, creating a continuous rightward push. Subsequent 'R's will override previous forces, maintaining the maximum propagation distance from the most recent 'R'.

9. Can we use DFS instead of BFS?

No, BFS is needed to process effects level by level (time steps). DFS would incorrectly simulate the propagation by going depth-first rather than processing all dominoes at each time step together.

10. What's the key insight for the optimal solution?

Forces can be calculated independently then combined, avoiding simulation. By separating the rightward and leftward force calculations, we can determine the net effect on each domino without explicitly modeling each time step.

Final Thoughts: This problem beautifully demonstrates how physical systems can be modeled algorithmically. The force propagation approach is particularly elegant, showing how careful analysis can lead to optimal solutions that avoid unnecessary simulation.