# Push Dominoes
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/push-dominoes)
Canonical: https://scaleengineer.com/dsa/problems/push-dominoes
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** String
---
## 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 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:**

![](https://assets.glich.co/dsa/push-dominoes/image0.png) 

**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
## Brute-Force Simulation
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.
**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.
**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.
### Explanation
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.

```java
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);
    }
}
```
### 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.

## Two-Pass Force Calculation
This approach determines the final state of each domino by calculating the net force acting upon it. We can think of an 'R' domino as exerting a rightward force that diminishes with distance, and an 'L' domino exerting a leftward force. By making two passes over the dominoes, we can compute the total force at each position and decide its final state.
**Time:** O(N), as the algorithm consists of two linear passes to calculate forces and one pass to build the result string. · **Space:** O(N) to store the `forces` array.
**Pros:** Efficient O(N) time complexity.; Systematically handles all interactions between 'L' and 'R' forces.
**Cons:** Requires extra O(N) space for the forces array.; Needs multiple passes over the data, which might be slightly less performant than a single-pass solution due to cache effects.
### Explanation
The core idea is that the state of any standing domino `.` is decided by the nearest `R` to its left and the nearest `L` to its right. We can quantify this by calculating forces. We use an auxiliary array, `forces`, to store the net force at each position.

First, we iterate from left to right. When we encounter an 'R', we start a 'rightward force' of magnitude `n`. This force decreases by 1 for each step we move to the right. An 'L' acts as a wall, stopping any rightward force from its left, so we reset the force to 0. We add this calculated force to our `forces` array.

Next, we do a similar pass from right to left to calculate 'leftward forces'. An 'L' starts a force, and an 'R' stops it. We subtract this leftward force from the `forces` array.

After both passes, the `forces` array contains the net force at each position. A positive value means the rightward force is stronger, a negative value means the leftward force is stronger, and zero means the forces are balanced or no force is present. We can then build the final string based on the sign of the force at each position.

```java
class Solution {
    public String pushDominoes(String dominoes) {
        int n = dominoes.length();
        int[] forces = new int[n];

        // Rightward forces from left to right
        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(0, force - 1);
            }
            forces[i] += force;
        }

        // Leftward forces from right to left
        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(0, force - 1);
            }
            forces[i] -= force;
        }

        StringBuilder result = new StringBuilder();
        for (int f : forces) {
            if (f > 0) {
                result.append('R');
            } else if (f < 0) {
                result.append('L');
            } else {
                result.append('.');
            }
        }

        return result.toString();
    }
}
```
### Algorithm
1. Create an integer array `forces` of size `n`, initialized to zeros.
2. **First Pass (Left to Right):** Calculate rightward forces.
   - Initialize a variable `force = 0`.
   - Iterate from `i = 0` to `n-1`:
     - If `dominoes[i] == 'R'`, set `force = n`.
     - If `dominoes[i] == 'L'`, reset `force = 0` (as 'L' blocks any rightward force from its left).
     - If `dominoes[i] == '.'`, decrement `force` (i.e., `force = Math.max(0, force - 1)`).
     - Add the current `force` to `forces[i]`.
3. **Second Pass (Right to Left):** Calculate leftward forces.
   - Reset `force = 0`.
   - Iterate from `i = n-1` to `0`:
     - If `dominoes[i] == 'L'`, set `force = n`.
     - If `dominoes[i] == 'R'`, reset `force = 0`.
     - If `dominoes[i] == '.'`, decrement `force`.
     - Subtract the current `force` from `forces[i]`.
4. **Build Result:**
   - Create a `StringBuilder`.
   - Iterate through the `forces` array:
     - If `forces[i] > 0`, append 'R'.
     - If `forces[i] < 0`, append 'L'.
     - If `forces[i] == 0`, append '.'.
5. Return the final string.

## One-Pass with Two Pointers (Segment Processing)
This is the most efficient approach, which processes the dominoes in a single pass. The key observation is that the string can be divided into independent segments of standing dominoes ('.') bordered by falling dominoes ('L' or 'R') or the ends of the string. The final state of the dominoes within each segment only depends on its two boundaries.
**Time:** O(N), as we iterate through the array with pointer `j` once. The inner loops for filling segments also contribute linearly to the total time, as each character is written to at most once. · **Space:** O(N). In Java, strings are immutable, so we need a `char` array or `StringBuilder` of size N to build the result. In languages with mutable strings, this could be an O(1) space solution.
**Pros:** Most efficient time complexity, O(N), with a single pass.; Processes the string in-place (on a char array), which can be memory efficient.
**Cons:** The logic for handling the different segment types and boundary conditions can be slightly more complex to write correctly compared to other approaches.
### Explanation
We can iterate through the string using a pointer `j` to find segments of `.`s. Another pointer, `i`, keeps track of the index of the previous non-`.` character (the left boundary of the current segment). When `res[j]` is 'L' or 'R', we have found a segment of `.`s from index `i+1` to `j-1`.

The behavior of this segment is determined entirely by its boundaries, `res[i]` and `res[j]`.
- **R...R**: All `.`s become `R`.
- **L...L**: All `.`s become `L`.
- **L...R**: The `.`s are not pushed by these boundaries, so they remain `.`.
- **R...L**: The forces collide. We fill the first half of the `.`s with `R` and the second half with `L`. If there's an odd number of `.`s, the middle one remains standing.

We also need to handle the edge cases where a segment is at the beginning or end of the string. We can imagine a virtual 'L' at index -1 and a virtual 'R' at index `n`. For example, a segment `...R` at the beginning is treated as `L...R`, so the `.`s don't fall. A segment `L...` at the end is treated as `L...R`, so again the `.`s don't fall. This logic allows us to solve the problem in a single, efficient pass.

```java
class Solution {
    public String pushDominoes(String dominoes) {
        char[] res = dominoes.toCharArray();
        int n = res.length;
        int i = -1; // Index of the last seen 'L' or 'R'

        for (int j = 0; j < n; ++j) {
            if (res[j] == '.') {
                continue;
            }
            if (i == -1) { // Segment starts at the beginning
                if (res[j] == 'L') {
                    for (int k = 0; k < j; ++k) {
                        res[k] = 'L';
                    }
                }
            } else { // Segment is between res[i] and res[j]
                if (res[i] == res[j]) { // R...R or L...L
                    for (int k = i + 1; k < j; ++k) {
                        res[k] = res[i];
                    }
                } else if (res[i] == 'R' && res[j] == 'L') { // R...L
                    int l = i + 1, r = j - 1;
                    while (l < r) {
                        res[l++] = 'R';
                        res[r--] = 'L';
                    }
                }
                // Case L...R is implicitly handled, as '.'s remain '.'
            }
            i = j;
        }

        if (i != -1 && res[i] == 'R') { // Segment ends at the end
            for (int k = i + 1; k < n; ++k) {
                res[k] = 'R';
            }
        }

        return new String(res);
    }
}
```
### Algorithm
1. Convert the input string to a `char` array `res` for in-place modification.
2. Use two pointers, `i` and `j`. Let `i` be the index of the last seen 'L' or 'R', initialized to -1.
3. Iterate `j` from `0` to `n` (inclusive, to handle the last segment).
4. When `j` reaches `n` or `res[j]` is not '.', we have identified a segment of '.'s between `i` and `j`.
5. Get the boundary characters: `leftChar` is `res[i]` (or 'L' if `i` is -1) and `rightChar` is `res[j]` (or 'R' if `j` is `n`).
6. Apply rules based on `leftChar` and `rightChar`:
   - If `leftChar == rightChar == 'R'`, fill the segment `res[i+1...j-1]` with 'R'.
   - If `leftChar == rightChar == 'L'`, fill the segment `res[i+1...j-1]` with 'L'.
   - If `leftChar == 'R'` and `rightChar == 'L'`, fill the segment from both ends towards the middle. Use two more pointers, `l=i+1` and `r=j-1`. In a loop while `l < r`, set `res[l++] = 'R'` and `res[r--] = 'L'`.
   - If `leftChar == 'L'` and `rightChar == 'R'`, do nothing, as the dominoes in between are not pushed.
7. After processing the segment, update `i = j` to start searching for the next segment.
8. Convert the modified `char` array back to a string.

# Solutions
### Java

```java
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 {}
```

### CPP

```cpp
class Solution {
public:
  string pushDominoes(string dominoes) {
    int n = dominoes.size();
    queue<int> q;
    vector<int> time(n, -1);
    vector<string> force(n);
    for (int i = 0; i < n; i++) {
      if (dominoes[i] == '.')
        continue;
      q.emplace(i);
      time[i] = 0;
      force[i].push_back(dominoes[i]);
    }
    string ans(n, '.');
    while (!q.empty()) {
      int i = q.front();
      q.pop();
      if (force[i].size() == 1) {
        char f = force[i][0];
        ans[i] = f;
        int j = (f == 'L') ? (i - 1) : (i + 1);
        if (j >= 0 && j < n) {
          int t = time[i];
          if (time[j] == -1) {
            q.emplace(j);
            time[j] = t + 1;
            force[j].push_back(f);
          } else if (time[j] == t + 1)
            force[j].push_back(f);
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def pushDominoes(self, dominoes: str) -> str: n = len(dominoes) q = deque() time = [- 1] * n force = defaultdict(list) for i, f in enumerate(dominoes): if f != '.': q . append(i) time[i] = 0 force[i]. append(f) ans = ['.'] * n while q: i = q . popleft() if len(force[i]) == 1: ans[i] = f = force[i][0] j = i - 1 if f == 'L' else i + 1 if 0 <= j < n: t = time[i] if time[j] == - 1: q . append(j) time[j] = t + 1 force[j]. append(f) elif time[j] == t + 1: force[j]. append(f) return '' . join(ans)

```