# LeetCode 838: Push Dominoes

## Problem Restatement

We are given a string `dominoes`.

Each character describes the initial state of one domino:

| Character | Meaning |
|---|---|
| `"L"` | Domino is pushed to the left |
| `"R"` | Domino is pushed to the right |
| `"."` | Domino is standing upright |

After each second, a falling domino pushes the adjacent upright domino in the same direction.

If a standing domino receives equal force from both sides at the same time, it stays upright.

A domino already falling or already fallen does not pass extra force through another falling domino.

Return the final state of all dominoes. The constraints allow strings up to length `10^5`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A string `dominoes` |
| Output | Final domino state as a string |
| Characters | `"L"`, `"R"`, and `"."` |
| Main rule | Forces spread one cell per second |
| Tie rule | Equal opposite forces cancel |

Function shape:

```python
class Solution:
    def pushDominoes(self, dominoes: str) -> str:
        ...
```

## Examples

Example 1:

```python
dominoes = "RR.L"
```

The final state is:

```python
"RR.L"
```

The left `"R"` side does not push through an already falling domino, so the middle state stays as given.

Example 2:

```python
dominoes = ".L.R...LR..L.."
```

The final state is:

```python
"LL.RR.LLRRLL.."
```

## First Thought: Simulate Every Second

A direct approach is to simulate time.

At each second:

1. Look at every upright domino.
2. Check whether it is pushed from the left, from the right, or both.
3. Build the next state.
4. Repeat until nothing changes.

This can work for small strings, but it is too slow.

A force may travel across a long row of dots. With `n` dominoes, simulation can take many rounds, and each round scans the string.

That can become:

```python
O(n^2)
```

We need a linear method.

## Key Insight

A domino's final state depends on the nearest effective force from the left and the nearest effective force from the right.

A right-pushing force `"R"` travels to the right until blocked by an `"L"`.

A left-pushing force `"L"` travels to the left until blocked by an `"R"`.

We can compute net force with two scans:

1. Left to right: measure force from `"R"`.
2. Right to left: measure force from `"L"`.

If the right force is stronger, the domino becomes `"R"`.

If the left force is stronger, the domino becomes `"L"`.

If they are equal, the domino stays `"."`.

## Algorithm

Let `n = len(dominoes)`.

Create an array `forces` of length `n`, initially all `0`.

First pass from left to right:

1. If we see `"R"`, set force to `n`.
2. If we see `"L"`, reset force to `0`.
3. If we see `"."`, decrease force by `1`, but not below `0`.
4. Add this force to `forces[i]`.

Second pass from right to left:

1. If we see `"L"`, set force to `n`.
2. If we see `"R"`, reset force to `0`.
3. If we see `"."`, decrease force by `1`, but not below `0`.
4. Subtract this force from `forces[i]`.

Finally:

| Net force | Final character |
|---|---|
| Positive | `"R"` |
| Negative | `"L"` |
| Zero | `"."` |

## Walkthrough

Use:

```python
dominoes = "R...L"
```

The `"R"` pushes right.

The `"L"` pushes left.

Positions:

```python
0 1 2 3 4
R . . . L
```

The middle dot at index `2` receives equal force from both sides.

Final state:

```python
"RR.LL"
```

Index `1` is closer to `"R"`, so it becomes `"R"`.

Index `3` is closer to `"L"`, so it becomes `"L"`.

Index `2` is equally close to both, so it stays `"."`.

## Correctness

The left-to-right pass computes, for each position, the strength of the nearest unblocked `"R"` force coming from the left.

When the scan sees `"R"`, a new rightward force begins. When it sees `"L"`, that rightward force is blocked. Between them, the force decreases by one per position, matching the one-cell-per-second propagation rule.

The right-to-left pass computes the analogous nearest unblocked `"L"` force from the right.

For each domino, the final direction is determined by comparing these two arrival strengths. A larger rightward force means the `"R"` wave arrives earlier, so the domino falls right. A larger leftward force means the `"L"` wave arrives earlier, so the domino falls left. Equal force means both waves arrive at the same time, so the domino stays upright.

Thus the algorithm assigns every domino exactly the final state implied by the simultaneous process.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Two linear scans and one output scan |
| Space | `O(n)` | The force array and output array |

## Implementation

```python
class Solution:
    def pushDominoes(self, dominoes: str) -> str:
        n = len(dominoes)
        forces = [0] * n

        force = 0
        for i, ch in enumerate(dominoes):
            if ch == "R":
                force = n
            elif ch == "L":
                force = 0
            else:
                force = max(force - 1, 0)

            forces[i] += force

        force = 0
        for i in range(n - 1, -1, -1):
            ch = dominoes[i]

            if ch == "L":
                force = n
            elif ch == "R":
                force = 0
            else:
                force = max(force - 1, 0)

            forces[i] -= force

        result = []

        for force in forces:
            if force > 0:
                result.append("R")
            elif force < 0:
                result.append("L")
            else:
                result.append(".")

        return "".join(result)
```

## Code Explanation

The force array stores the net force at each position:

```python
forces = [0] * n
```

In the left-to-right pass:

```python
if ch == "R":
    force = n
elif ch == "L":
    force = 0
else:
    force = max(force - 1, 0)
```

An `"R"` starts a strong rightward force.

An `"L"` blocks rightward force.

A dot receives the previous force weakened by one.

We add that rightward force:

```python
forces[i] += force
```

In the right-to-left pass, we do the same for leftward force, but subtract it:

```python
forces[i] -= force
```

Finally, positive net force becomes `"R"`, negative net force becomes `"L"`, and zero becomes `"."`.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.pushDominoes("RR.L") == "RR.L"
    assert s.pushDominoes(".L.R...LR..L..") == "LL.RR.LLRRLL.."
    assert s.pushDominoes("R...L") == "RR.LL"
    assert s.pushDominoes("R..L") == "RRLL"
    assert s.pushDominoes("...") == "..."
    assert s.pushDominoes("L....") == "L...."
    assert s.pushDominoes("....R") == "....R"

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `"RR.L"` | Confirms force does not pass through a fallen domino |
| Standard example | Confirms mixed interactions |
| `"R...L"` | Confirms equal forces leave middle upright |
| `"R..L"` | Confirms no middle when distance is even |
| All dots | Confirms no force |
| Leading left push | Confirms left force does not move right |
| Trailing right push | Confirms right force does not move left |