Push Dominoes
MedPrompt
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'.'.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly simulates the process of dominoes falling second by second. We repeatedly scan the line of dominoes and update their states based on their neighbors. A standing domino falls if pushed from one side but not the other. This process continues until no more dominoes can fall, and the configuration becomes stable.
Algorithm
- Initialize a
chararraycurrentStatefrom the inputdominoesstring. - Start a loop that continues as long as changes are made to the dominoes' state in an iteration.
- Inside the loop, create a
nextStatecharacter array, initially a copy ofcurrentState. - Set a boolean flag
changedtofalse. - Iterate from
i = 0ton-1through thecurrentState. - If
currentState[i]is '.':- Check for a right push from the left neighbor:
pushR = (i > 0 && currentState[i-1] == 'R'). - Check for a left push from the right neighbor:
pushL = (i < n-1 && currentState[i+1] == 'L'). - If
pushRis true andpushLis false, setnextState[i] = 'R'andchanged = true. - If
pushLis true andpushRis false, setnextState[i] = 'L'andchanged = true.
- Check for a right push from the left neighbor:
- After the inner loop, update
currentStatewithnextState. - If
changedisfalse, break the outer loop as the state is stable. - Convert the final
currentStatearray back to a string and return it.
Walkthrough
The brute-force simulation mimics the physical process described in the problem. We treat each pass over the dominoes array as one second of time. In each pass, we determine the next state of all dominoes simultaneously. A standing domino . at index i will fall to the right if its left neighbor i-1 is an R, and it will fall to the left if its right neighbor i+1 is an L. If it's pushed from both sides, the forces balance, and it remains standing. We use a temporary array to store the state for the next second to ensure all changes are based on the state from the current second. We repeat this process until a full pass results in no changes, indicating a final, stable state.
class Solution { public String pushDominoes(String dominoes) { int n = dominoes.length(); char[] current = dominoes.toCharArray(); char[] next = new char[n]; boolean changed = true; while (changed) { changed = false; System.arraycopy(current, 0, next, 0, n); for (int i = 0; i < n; i++) { if (current[i] == '.') { boolean pushR = (i > 0 && current[i - 1] == 'R'); boolean pushL = (i < n - 1 && current[i + 1] == 'L'); if (pushR && !pushL) { next[i] = 'R'; changed = true; } else if (pushL && !pushR) { next[i] = 'L'; changed = true; } } } System.arraycopy(next, 0, current, 0, n); } return new String(current); }}Complexity
Time
O(N^2), where N is the number of dominoes. In the worst-case scenario (e.g., `R.......`), a force propagates one step at a time, requiring N iterations. Each iteration involves a scan of the entire array, taking O(N) time.
Space
O(N), where N is the number of dominoes. This is for the auxiliary array used to store the state of the dominoes in the next second.
Trade-offs
Pros
Intuitive and easy to understand as it directly models the problem statement.
Relatively simple to implement.
Cons
Highly inefficient for large inputs, likely to result in a 'Time Limit Exceeded' error.
The number of iterations can be up to N, making the overall complexity quadratic.
Solutions
Solution
public class Solution { public String pushDominoes ( String dominoes ) { int n = dominoes . length (); Deque < Integer > q = new ArrayDeque <>(); int [] time = new int [ n ]; Arrays . fill ( time , - 1 ); List < Character >[] force = new List [ n ]; for ( int i = 0 ; i < n ; ++ i ) { force [ i ] = new ArrayList <>(); } for ( int i = 0 ; i < n ; ++ i ) { char f = dominoes . charAt ( i ); if ( f != '.' ) { q . offer ( i ); time [ i ] = 0 ; force [ i ]. add ( f ); } } char [] ans = new char [ n ]; Arrays . fill ( ans , '.' ); while (! q . isEmpty ()) { int i = q . poll (); if ( force [ i ]. size () == 1 ) { ans [ i ] = force [ i ]. get ( 0 ); char f = ans [ i ]; int j = f == 'L' ? i - 1 : i + 1 ; if ( j >= 0 && j < n ) { int t = time [ i ]; if ( time [ j ] == - 1 ) { q . offer ( j ); time [ j ] = t + 1 ; force [ j ]. add ( f ); } else if ( time [ j ] == t + 1 ) { force [ j ]. add ( f ); } } } } return new String ( ans ); } } class Solution {}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.