838. Push Dominoes

MediumTwo PointersStringDynamic Programming

Problem Description

In this problem, we're given a line of dominoes represented by a string of characters, with each character indicating the state of a domino. A domino can either be standing vertically (.), pushed to the left (L), or pushed to the right (R). The string represents the initial configuration of the dominoes at time zero.

When dominoes are pushed, they start falling and can cause adjacent dominoes to fall as well. If a domino is pushed to the left, it will make its left neighbor fall to the left in the next second, and similarly for the right. However, if dominoes are falling towards each other, they will make the domino in between them stand still (.) as the forces from both sides will cancel.

The objective is to determine the final state of all dominoes after all movements have stopped – which is when no further dominoes are being pushed over by their neighbors.

Intuition

The solution approach deals with the propagation of the falling action among dominoes. A key observation is to keep track of the time it takes for each domino to fall and the direction of the force applied to it. By initializing a queue to store the indices of dominoes that have been pushed, we can process each one by one.

We use Breadth-First Search (BFS) to simulate the domino effect. BFS is useful for problems where we need to propagate information (or in this case, force) level by level, from neighbor to neighbor. We start by adding indices with 'L' or 'R' to the queue and setting their time to 0 since these are the starting points of the falling process.

As we dequeue an index, we apply its force to its respective neighbor if the conditions allow - that is if the neighbor hasn’t been pushed (time[j] is -1) or at the same time from the opposite side (time[j] == t + 1). If a domino receives force from both sides at the same time, it will remain standing – which is ensured by storing all forces in a force list and checking its length. When a domino gets only one direction of force, we proceed with the domino effect in that direction, queuing up the next domino in line.

In the end, we join and return the resulted string, which is the final state of the dominoes.

Learn more about Two Pointers and Dynamic Programming patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following is the prefix sum of array [1, 2, 3, 4, 5]?

[1, 2, 3, 4, 5][1, 3, 6, 10, 15][15, 14, 12, 9, 5][5, 4, 3, 2, 1]

I don’t know

Solution Approach

The implementation uses a combination of Breadth-First Search (BFS), a queue, a time array, and a force dictionary – each element playing a specific role in simulating the domino effect.

Data Structures:

Queue (q): A double-ended queue deque is used for BFS to store the indices of the dominoes that are currently falling. It allows us to easily add new dominoes that start falling and process dominoes in the order they were pushed.
Time Array (time): An array that holds the time at which each domino falls. If a domino has not fallen, it is marked with -1. This helps in determining if a neighboring domino should be pushed (if it is still untouched) or to detect simultaneous pushes (a domino pushed at the same time from both sides).
Force Dictionary (force): A defaultdict with list values used to track all forces acting on a domino. If a domino is pushed at the same time from both sides, this can be detected when the length of the list for that index is greater than 1.

Algorithm:

Iterate through the dominoes string, and for each domino that is not upright ('.'), initialize the time at this index to 0 and add the forces acting on it to the force dictionary. Also, each such domino’s index is added to the q.
Start processing the queue until it's empty:
- Dequeue an index i and check the forces acting on it.
- If there’s only one force (len(force[i]) == 1):
  - Set the ans array at position i to the current force f.
  - Calculate the index j of the adjacent domino to push based on the current force's direction (j = i - 1 if f == 'L' and j = i + 1 if f == 'R').
  - If j is within bounds:
    - If the neighbor has not been pushed yet (time[j] == -1), update its time to t + 1, add its force, and enqueue index j.
    - If the neighbor is being pushed at the same time (time[j] == t + 1), add the force to it.
Once the queue is empty, join the ans array into a string representing the final state of the dominoes and return it.

By following this approach, the algorithm simulates the force propagation, domino interaction, and stabilization to output the final arrangement of dominoes.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Example Walkthrough

Let's illustrate the solution approach with a small example, using the initial string of dominoes ..R...L... Here's how the algorithm processes this string:

Initialize data structures:
- dominoes: ..R...L..
- q: []
- time: [-1, -1, 0, -1, -1, -1, 0, -1, -1]
- force: {2: ['R'], 6: ['L']}
- ans: ['.', '.', '.', '.', '.', '.', '.', '.', '.']
Fill the queue with indices of pushed dominoes and their respective times and forces:
- The domino at index 2 is pushed to the right, so we add 2 to q.
- The domino at index 6 is pushed to the left, so we add 6 to q.
Process the queue:
- Dequeue index 2, the force is ['R'], so we push the domino at index 3.
- Dequeue index 6, the force is ['L'], so we push the domino at index 5.
Continue the BFS:
- At index 3, since there was no push from the left, the domino falls to the right and we enqueue index 4 with a time of 1 (previous time + 1).
- At index 5, since there is no push from the right, the domino falls to the left and we enqueue index 4 with a time of 1.
Resolve conflicts:
- At index 4, we have enqueued this index twice (once from the right and once from the left) both with time 1. When dequeued, the force dictionary shows two forces acting on this domino, ['R', 'L'], so it stays upright.
Output the final state:
- Since there are no more dominoes to process, we concatenate our finalized ans array to get the final state of the dominoes: ..RR.L....

In this way, using BFS and the associated data structures, we've efficiently simulated the entire domino chain-reaction and have arrived at the final arrangement without any iterative comparison.

Solution Implementation

1from collections import deque, defaultdict
2
3class Solution:
4    def pushDominoes(self, dominoes: str) -> str:
5        # Length of the dominoes string
6        num_dominoes = len(dominoes)
7      
8        # Queue to hold the indices of dominoes to process
9        queue = deque()
10      
11        # Array to hold the time when each dominoe falls
12        fall_time = [-1] * num_dominoes
13      
14        # Dictionary to hold the force(s) acting on each dominoe
15        forces = defaultdict(list)
16      
17        # Initialize the queue, fall_time, and forces
18        for index, force in enumerate(dominoes):
19            if force != '.':
20                queue.append(index)
21                fall_time[index] = 0
22                forces[index].append(force)
23      
24        # Resultant dominoes state
25        result = ['.'] * num_dominoes
26      
27        # Process the queue
28        while queue:
29            current_idx = queue.popleft()
30            if len(forces[current_idx]) == 1:
31                resultant_force = forces[current_idx][0]
32                result[current_idx] = resultant_force
33                next_idx = current_idx - 1 if resultant_force == 'L' else current_idx + 1
34                if 0 <= next_idx < num_dominoes:
35                    current_time = fall_time[current_idx]
36                    if fall_time[next_idx] == -1:
37                        queue.append(next_idx)
38                        fall_time[next_idx] = current_time + 1
39                        forces[next_idx].append(resultant_force)
40                    elif fall_time[next_idx] == current_time + 1:
41                        forces[next_idx].append(resultant_force)
42      
43        # Return the final dominoes state as a string
44        return ''.join(result)
45
46# The code now uses more standard and descriptive variable names.
47# Additionally, the comments provide a clear explanation of each part of the algorithm.
48

1public class Solution {
2    public String pushDominoes(String dominoes) {
3        int length = dominoes.length();
4        // Queue to keep track of indices in the dominoes string that are affected by forces
5        Deque<Integer> queue = new ArrayDeque<>();
6        // Array to keep track of the time when each force reaches an index
7        int[] times = new int[length];
8        // Initialize all times to -1 (indicating no force has reached the index)
9        Arrays.fill(times, -1);
10        // List to store forces affecting each index (as multiple forces can affect the same index)
11        List<Character>[] forces = new List[length];
12        for (int i = 0; i < length; ++i) {
13            forces[i] = new ArrayList<>();
14        }
15      
16        // Initialize the forces and times with the initial state. Also add indices to queue to process
17        for (int i = 0; i < length; ++i) {
18            char force = dominoes.charAt(i);
19            if (force != '.') {
20                queue.offer(i);
21                times[i] = 0;
22                forces[i].add(force);
23            }
24        }
25      
26        // Array to store the final state of the dominoes
27        char[] result = new char[length];
28        Arrays.fill(result, '.');
29      
30        // Process the queue until it is empty
31        while (!queue.isEmpty()) {
32            int idx = queue.poll();
33            // If only one force is affecting the index, update the result
34            if (forces[idx].size() == 1) {
35                char force = forces[idx].get(0);
36                result[idx] = force;
37                int nextIdx = force == 'L' ? idx - 1 : idx + 1;
38                if (nextIdx >= 0 && nextIdx < length) {
39                    int currentTime = times[idx];
40                    if (times[nextIdx] == -1) {
41                        queue.offer(nextIdx);
42                        times[nextIdx] = currentTime + 1;
43                        forces[nextIdx].add(force);
44                    } else if (times[nextIdx] == currentTime + 1) {
45                        forces[nextIdx].add(force);
46                    }
47                }
48            }
49        }
50      
51        // Convert char array to string and return
52        return new String(result);
53    }
54}
55

1class Solution {
2public:
3    string pushDominoes(string dominoes) {
4        int numDominoes = dominoes.size(); // Get the size of the string representing the dominoes.
5      
6        // Queue to keep track of indices of dominoes which have been tipped or will be tipped.
7        queue<int> waitingQueue;
8      
9        // Vector to store the time at which each domino is tipped. Initialize with -1 (untipped).
10        vector<int> tipTime(numDominoes, -1);
11      
12        // Vector of strings to store the forces acting on each domino. 
13        // Multiple forces can only act during the same time unit, hence using strings.
14        vector<string> forces(numDominoes);
15      
16        for (int i = 0; i < numDominoes; i++) {
17            if (dominoes[i] == '.') continue; // Skip if the domino has not been tipped.
18            waitingQueue.emplace(i); // Add the index to the queue.
19            tipTime[i] = 0; // Tipped at time 0 (initial state)
20            forces[i].push_back(dominoes[i]); // Record the initial force ('L' or 'R')
21        }
22
23        // String to store the final state of the dominoes.
24        string finalState(numDominoes, '.');
25      
26        // Process each domino in the queue.
27        while (!waitingQueue.empty()) {
28            int index = waitingQueue.front(); // Get the current index to be processed.
29            waitingQueue.pop();
30          
31            // If only one force is acting on the domino, process it.
32            if (forces[index].size() == 1) {
33                char forceDirection = forces[index][0]; // Get the force direction 'L' or 'R'.
34                finalState[index] = forceDirection; // Tip the domino in the final state.
35              
36                // Calculate the adjacent index. Left for 'L', Right for 'R'.
37                int adjacentIndex = (forceDirection == 'L') ? (index - 1) : (index + 1);
38              
39                // Check if the adjacent index is within bounds.
40                if (adjacentIndex >= 0 && adjacentIndex < numDominoes) {
41                    int currentTime = tipTime[index]; // Get the current time.
42                  
43                    // Tip the next domino if it hasn't been tipped yet.
44                    if (tipTime[adjacentIndex] == -1) {
45                        waitingQueue.emplace(adjacentIndex); // Add index to the queue.
46                        tipTime[adjacentIndex] = currentTime + 1; // Update the time.
47                        forces[adjacentIndex].push_back(forceDirection); // Apply the force.
48                    // If the next domino is tipped at the same time, it means forces are colliding.
49                    } else if (tipTime[adjacentIndex] == currentTime + 1)
50                        forces[adjacentIndex].push_back(forceDirection); // Forces collide.
51                }
52            }
53            // Collision case is implicitly handled by not tipping the domino in the final state.
54        }
55      
56        return finalState; // Return the final state of the dominoes 
57    }
58};
59

1function pushDominoes(dominoes: string): string {
2    const length = dominoes.length;
3    // Mapping the input characters to numerical values for easy processing
4    const dominoMap = {
5        'L': -1,
6        'R': 1,
7        '.': 0,
8    };
9    // Initialize the result array with numerical values
10    let result = new Array(length).fill(0);
11    // Track visited positions with their propagation depth
12    let visited = new Array(length).fill(0);
13    // Queue for BFS (Breadth-First Search) to track dominos to process
14    let queue: number[] = [];
15    // Start with depth 1 (first level of BFS)
16    let currentDepth = 1;
17
18    // Set up the queue with initial domino positions
19    for (let index = 0; index < length; index++) {
20        let dominoValue = dominoMap[dominoes.charAt(index)];
21        if (dominoValue) {
22            queue.push(index);
23            visited[index] = currentDepth;
24            result[index] = dominoValue;
25        }
26    }
27
28    // Process the queue using BFS
29    while (queue.length) {
30        currentDepth++;
31        let nextLevel: number[] = [];
32        for (let position of queue) {
33            const direction = result[position];
34            let newPosition = position + direction;
35            // If not out of bounds and not visited at current level or blocked
36            if (newPosition >= 0 && newPosition < length && [0, currentDepth].includes(visited[newPosition])) {
37                result[newPosition] += direction;
38                visited[newPosition] = currentDepth;
39                nextLevel.push(newPosition);
40            }
41        }
42        queue = nextLevel;
43    }
44
45    // Convert the numerical result back into domino state characters
46    return result
47        .map(value => {
48            if (value === 0) return '.';
49            else if (value < 0) return 'L';
50            else return 'R';
51        })
52        .join('');
53}
54

Not Sure What to Study? Take the 2-min Quiz：

Time and Space Complexity

The given code simulates the process of pushing dominoes. Let n be the length of the string dominoes. The time complexity and space complexity analysis are as follows:

Time Complexity:

The initialization of time and force, as well as the enumeration of dominoes to populate the queue q: O(n), since every domino is processed once.
The while loop processes each domino at most twice - once for each possible push direction ('L' or 'R'). The main processing within the while loop executes in constant time for each element, except for the deque operations.
The popleft operation from deque q is O(1) amortized per element.
Checking and updating the force at index j is also O(1) for each element since list append and length check are constant time operations.
Hence, every element can be inserted into the queue at most twice, once for being pushed to the left, and once for being pushed to the right.

The overall time complexity of the loop is O(n), because each element is dealt with in constant time and the queue ensures that each element is processed at most twice. Therefore, the total time complexity is O(n) + O(n) = O(n).

Space Complexity:

The time list, force dictionary, and ans list each require O(n) space.
The q can have at most n elements in the worst case when all dominoes are getting pushed.
The force dictionary has lists, but each index i in force will have at most two forces (pushed from left and right) if dominoes at index i falls due to being pushed by both sides. So, space required by force values (lists) still remains within O(n) overall.

Thus, the space complexity is O(n) + O(n) + O(n) = O(n).

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

Fast Track Your Learning with Our Quick Skills Quiz:

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

838. Push Dominoes

Problem Description

Intuition

Solution Approach

Data Structures:

Algorithm:

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity:

Space Complexity: