Scale Engineer

Push Dominoes

Med
#0792Time: 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.
Patterns
Two PointersDynamic Programming
Data structures
String

Prompt

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 the ith domino has been pushed to the left,
  • dominoes[i] = 'R', if the ith domino has been pushed to the right, and
  • dominoes[i] = '.', if the ith domino 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.length
  • 1 <= n <= 105
  • dominoes[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

  1. Initialize a char array currentState from the input dominoes string.
  2. Start a loop that continues as long as changes are made to the dominoes' state in an iteration.
  3. Inside the loop, create a nextState character array, initially a copy of currentState.
  4. Set a boolean flag changed to false.
  5. Iterate from i = 0 to n-1 through the currentState.
  6. 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 pushR is true and pushL is false, set nextState[i] = 'R' and changed = true.
    • If pushL is true and pushR is false, set nextState[i] = 'L' and changed = true.
  7. After the inner loop, update currentState with nextState.
  8. If changed is false, break the outer loop as the state is stable.
  9. Convert the final currentState array 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

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.

← Previous

Previous problem

Next →

Next problem