Push Dominoes solution and explanation
Google
9 more videos on this problem
Push Dominoes - Leetcode 838 - PythonNeetCode · 17:39 · 29K views
Push Dominoes | Simplest Intuition | Complete Dry Run | Leetcode 838 | codestorywithMIKcodestorywithMIK · 40:06 · 12K views
LeetCode Push Dominoes Solution Explained - JavaNick White · 11:40 · 10K views
Push Dominoes | Leetcode 838 | Live Coding session 🔥🔥🔥Coding Decoded · 20:46 · 4K views
Push Dominoes | Leetcode 838Techdose · 19:23 · 4K views
LeetCode 838. Push Dominoes - Interview Prep Ep 108Fisher Coder · 19:40 · 1K views
Daily Leetcode #477: Jul 21, 2021 - 838. Push DominoesProgramming Live with Larry · 11:52 · 593 views
Push Dominoes #838 Leetcode daily challenge solution explanationXplore360 Training Solutions (Xplore360) · 14:46 · 544 views
838. Push Dominoes | Leetcode Daily - PythonLeetcode Daily · 7:57 · 243 views
838 Push Dominoes | Medium Level Question Push Dominoes | leetcode 138 solutionEduEverybody · 18:12 · 226 views
The problem
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 theithdomino has been pushed to the left,dominoes[i] = 'R', if theithdomino has been pushed to the right, anddominoes[i] = '.', if theithdomino 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.length1 <= n <= 105dominoes[i]is either'L','R', or'.'.
Approach overview
Problem Overview: You get a string representing dominoes. Each character is 'L', 'R', or '.'. When a domino falls left or right, it pushes the next domino in that direction. The task is to compute the final state after all forces propagate and the system stabilizes.
Approach 1: Two Pass Force Calculation (O(n) time, O(n) space)
This approach models the force exerted by falling dominoes. Scan the array from left to right and track the influence of 'R' pushes. Each step decreases the force as it moves away from the source. Store this force in an array. Then run a second pass from right to left to track 'L' forces. Subtract the right force from the left force at each index. Positive values mean right push wins, negative values mean left push wins, and zero means the domino remains upright. The method works because each domino only depends on the nearest pushing force in either direction. Complexity stays O(n) time with O(n) auxiliary space for the force array.
This technique relies on simple array scans and works well for problems involving directional influence across a string. The two directional sweeps resemble a two pointers pattern where influence propagates from both ends.
Approach 2: Simulate using Queue (O(n) time, O(n) space)
This approach treats the process as a time-based simulation. Start by pushing all initially falling dominoes ('L' and 'R') into a queue with their index and direction. Process the queue using a BFS-style loop. When a domino falls, it attempts to push its neighbor. If the neighbor is upright ('.'), mark it with the direction and enqueue it for the next step. Conflicts happen when two forces reach a domino simultaneously from opposite directions; in that case the domino stays upright. The queue ensures events are processed in chronological order, making the simulation accurate and still linear in time.
The queue-based simulation mirrors propagation problems often solved with dynamic programming style state updates or BFS expansion. It is intuitive and easier to reason about when visualizing the domino effect.
Recommended for interviews: The two-pass force calculation is typically preferred. It runs in linear time, uses simple arrays, and avoids explicit simulation. Interviewers like it because it demonstrates pattern recognition and efficient traversal. The queue simulation is still valuable since it mirrors the real physical process and clearly handles conflicts between opposing forces.
Approach 1: Approach 1: Two Pass Force Calculation
In this approach, we simulate the forces acting on the dominoes as a one-dimensional array of forces. Initially, each domino has zero force. We perform two passes: from left to right, and then from right to left. In the first pass, we apply forces caused by 'R' and increase the force gradually by 1 for each subsequent domino. In the second pass, we apply forces caused by 'L' and decrease the force by 1 for each subsequent domino. Finally, the resultant force at each position determines whether the domino remains upright (force=0), falls to the right (force>0), or falls to the left (force<0).
def pushDominoes(dominoes):
n = len(dominoes)
forces = [0] * n
# Calculate right forces
force = 0
for i in range(n):
if dominoes[i] == 'R':
force = n # A large force imposed by R
elif dominoes[i] == 'L':
force = 0 # No force given by L
else:
force = max(force - 1, 0)
forces[i] = force
# Calculate left forces
force = 0
for i in range(n - 1, -1, -1):
if dominoes[i] == 'L':
force = n # A large force imposed by L
elif dominoes[i] == 'R':
force = 0 # No force given by R
else:
force = max(force - 1, 0)
forces[i] -= force
# Determine the final state
result = []
for f in forces:
if f == 0:
result.append('.')
elif f > 0:
result.append('R')
else:
result.append('L')
return ''.join(result)function pushDominoes(dominoes) {
const n = dominoes.length;
const forces = Array(n).fill(0);
// Calculate right forces
let force = 0;
for (let i = 0; i < n; i++) {
if (dominoes[i] === 'R') {
force = n;
} else if (dominoes[i] === 'L') {
force = 0;
} else {
force = Math.max(force - 1, 0);
}
forces[i] = force;
}
// Calculate left forces
force = 0;
for (let i = n - 1; i >= 0; i--) {
if (dominoes[i] === 'L') {
force = n;
} else if (dominoes[i] === 'R') {
force = 0;
} else {
force = Math.max(force - 1, 0);
}
forces[i] -= force;
}
// Determine the final state
return forces.map(f => f === 0 ? '.' : (f > 0 ? 'R' : 'L')).join('');
}#include <string.h>
#include <stdlib.h>
char* pushDominoes(char* dominoes) {
int n = strlen(dominoes);
int* forces = (int*)calloc(n, sizeof(int));
char* result = (char*)malloc((n + 1) * sizeof(char));
int i, force = 0;
// Calculate right forces
for (i = 0; i < n; ++i) {
if (dominoes[i] == 'R') {
force = n; // A large force imposed by R
} else if (dominoes[i] == 'L') {
force = 0; // No force given by L
} else {
force = force > 0 ? force - 1 : 0;
}
forces[i] = force;
}
// Calculate left forces
for (i = n - 1; i >= 0; --i) {
if (dominoes[i] == 'L') {
force = n; // A large force imposed by L
} else if (dominoes[i] == 'R') {
force = 0; // No force given by R
} else {
force = force > 0 ? force - 1 : 0;
}
forces[i] -= force;
}
// Determine the final state
for (i = 0; i < n; ++i) {
if (forces[i] == 0) {
result[i] = '.';
} else if (forces[i] > 0) {
result[i] = 'R';
} else {
result[i] = 'L';
}
}
result[n] = '\0'; // Null-terminate the string
free(forces);
return result;
}The function uses a two-pass scanning to compute the forces acting on each domino. It first collects forces exerted by 'R's as positive values and reduces them across dominoes. Then, it collects forces exerted by 'L's as negative values, reducing these forces as well. By summing these forces, we decide the final state of each domino based on the net force.
Time complexity: O(n), where n is the number of dominoes since we traverse the dominoes twice.
Space complexity: O(n) due to the 'forces' array.
Approach 2: Approach 2: Simulate using Queue
This approach is also efficient and leverages a queue to process and simulate the domino effect until stability. We maintain a queue that handles dominos that need to be processed next, checking to apply the effect of the nearest 'L' or 'R'. This is somewhat similar to breadth-first search (BFS) in tree/graph traversal.
import java.util.*;
public class PushDominoes {
public String pushDominoes(String dominoes) {
int n = dominoes.length();
char[] result = dominoes.toCharArray();
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < n; i++) {
if (dominoes.charAt(i) != '.') {
queue.offer(i);
}
}
while (!queue.isEmpty()) {
int i = queue.poll();
char d = result[i];
if (d == 'L' && i > 0 && result[i - 1] == '.') {
result[i - 1] = 'L';
queue.offer(i - 1);
}
if (d == 'R' && i + 1 < n && result[i + 1] == '.') {
if (i + 2 < n && result[i + 2] == 'L') { // Balanced
continue;
}
result[i + 1] = 'R';
queue.offer(i + 1);
}
}
return new String(result);
}
}#include <queue>
#include <string>
class Solution {
public:
std::string pushDominoes(std::string dominoes) {
int n = dominoes.size();
std::string result = dominoes;
std::queue<int> queue;
for (int i = 0; i < n; ++i) {
if (dominoes[i] != '.') {
queue.push(i);
}
}
while (!queue.empty()) {
int i = queue.front(); queue.pop();
char d = result[i];
if (d == 'L' && i > 0 && result[i - 1] == '.') {
result[i - 1] = 'L';
queue.push(i - 1);
}
if (d == 'R' && i + 1 < n && result[i + 1] == '.') {
if (i + 2 < n && result[i + 2] == 'L') {
continue;
}
result[i + 1] = 'R';
queue.push(i + 1);
}
}
return result;
}
};using System;
using System.Collections.Generic;
public class Solution {
public string PushDominoes(string dominoes) {
int n = dominoes.Length;
char[] result = dominoes.ToCharArray();
Queue<int> queue = new Queue<int>();
for (int i = 0; i < n; ++i) {
if (dominoes[i] != '.') {
queue.Enqueue(i);
}
}
while (queue.Count > 0) {
int i = queue.Dequeue();
char d = result[i];
if (d == 'L' && i > 0 && result[i - 1] == '.') {
result[i - 1] = 'L';
queue.Enqueue(i - 1);
}
if (d == 'R' && i + 1 < n && result[i + 1] == '.') {
if (i + 2 < n && result[i + 2] == 'L') {
continue;
}
result[i + 1] = 'R';
queue.Enqueue(i + 1);
}
}
return new string(result);
}
}This solution uses a queue to simulate the domino fall process by looking through each 'R' or 'L' in the sequence and checking subsequent dominoes, applying rules as necessary (balancing too). As dominoes fall, they are added to the queue until all possibilities are exhausted.
Time complexity: O(n), since each domino movement is processed exactly once.
Space complexity: O(n), due to the queue storing no more than all domino positions.
Approach 3: Multi-Source BFS
Treat all initially pushed dominoes (L or R) as sources, which simultaneously propagate their forces outward. Use a queue to perform BFS layer by layer (0, 1, 2, ...):
We define time[i] to record the first moment when the i-th domino is affected by a force, with -1 indicating it has not been affected yet. We also define force[i] as a variable-length list that stores the directions ('L', 'R') of forces acting on the domino at the same moment. Initially, push all indices of L/R dominoes into the queue and set their time to 0.
When dequeuing index i, if force[i] contains only one direction, the domino will fall in that direction f. Let the index of the next domino be:
$
j =
\begin{cases}
i - 1, & f = L,\
i + 1, & f = R.
\end{cases}
If 0 leq j < n:
- If time[j] = -1
, it means j has not been affected yet. Recordtime[j] = time[i] + 1, enqueue it, and appendftoforce[j]. - If time[j] = time[i] + 1
, it means j has already been affected by another force at the same "next moment." In this case, appendftoforce[j], causing a standoff. Subsequently, sincelen(force[j]) = 2, it will remain upright.
After the queue is emptied, all positions where force[i] has a length of 1 will fall in the corresponding direction, while positions with a length of 2 will remain as .. Finally, concatenate the character array to form the answer.
The complexity is O(n), and the space complexity is O(n), where n$ is the number of dominoes.
function pushDominoes(dominoes: string): string {
const n = dominoes.length;
const q: number[] = [];
const time: number[] = Array(n).fill(-1);
const force: string[][] = Array.from({ length: n }, () => []);
for (let i = 0; i < n; i++) {
const f = dominoes[i];
if (f !== '.') {
q.push(i);
time[i] = 0;
force[i].push(f);
}
}
const ans: string[] = Array(n).fill('.');
let head = 0;
while (head < q.length) {
const i = q[head++];
if (force[i].length === 1) {
const f = force[i][0];
ans[i] = f;
const j = f === 'L' ? i - 1 : i + 1;
if (j >= 0 && j < n) {
const t = time[i];
if (time[j] === -1) {
q.push(j);
time[j] = t + 1;
force[j].push(f);
} else if (time[j] === t + 1) {
force[j].push(f);
}
}
}
}
return ans.join('');
}func pushDominoes(dominoes string) string {
n := len(dominoes)
q := []int{}
time := make([]int, n)
for i := range time {
time[i] = -1
}
force := make([][]byte, n)
for i, c := range dominoes {
if c != '.' {
q = append(q, i)
time[i] = 0
force[i] = append(force[i], byte(c))
}
}
ans := bytes.Repeat([]byte{'.'}, n)
for len(q) > 0 {
i := q[0]
q = q[1:]
if len(force[i]) > 1 {
continue
}
f := force[i][0]
ans[i] = f
j := i - 1
if f == 'R' {
j = i + 1
}
if 0 <= j && j < n {
t := time[i]
if time[j] == -1 {
q = append(q, j)
time[j] = t + 1
force[j] = append(force[j], f)
} else if time[j] == t+1 {
force[j] = append(force[j], f)
}
}
}
return string(ans)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Two Pass Force Calculation | Time complexity: O(n), where n is the number of dominoes since we traverse the dominoes twice. |
| Approach 2: Simulate using Queue | Time complexity: O(n), since each domino movement is processed exactly once. |
| Multi-Source BFS | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Pass Force Calculation | O(n) | O(n) | Best general solution. Efficient linear scan and commonly expected in interviews. |
| Queue Simulation (BFS) | O(n) | O(n) | Good when modeling time-based propagation or explaining the physical domino process clearly. |
Frequently asked questions
Is Push Dominoes easy or hard?
Push Dominoes is generally considered a medium difficulty problem. The naive simulation is straightforward, but finding the optimal O(n) force propagation approach requires recognizing directional influence patterns across the string.
How to solve Push Dominoes in O(n)?
Use a two-pass force propagation technique. First traverse left to right to track the decreasing force from 'R' dominoes. Then traverse right to left to track 'L' forces. Compare both forces at every index to determine whether the domino falls left, right, or stays upright. This requires only linear scans of the array.
Push Dominoes Python or Java solution?
Both Python and Java implementations follow the same algorithm. In Python, use arrays to store force values and update the final string. In Java, the same two-pass traversal or queue-based simulation can be implemented using arrays and a standard queue structure.
What is the best approach for Push Dominoes?
The most efficient approach is the two-pass force calculation. Scan left to right to compute the influence of 'R' pushes, then scan right to left for 'L' pushes. Combine both forces to determine the final state of each domino. This method runs in O(n) time with O(n) space and avoids explicit simulation.
Is Push Dominoes asked at Google/Amazon/Meta?
Push Dominoes is a common medium-level interview problem asked at companies like Google, Amazon, and Meta. It tests simulation, string processing, and the ability to optimize from naive simulation to linear-time propagation logic.
What data structure is used in Push Dominoes?
Typical solutions use arrays to store force values or a queue for simulation. The two-pass solution relies on an auxiliary array to track directional forces, while the BFS approach uses a queue to process domino pushes in time order.
What is the time complexity of Push Dominoes?
The optimal solutions run in O(n) time where n is the length of the domino string. Each domino is processed at most twice in the two-pass force approach. The queue-based simulation also stays O(n) because every domino is pushed into the queue at most once.