# LeetCode 755: Pour Water

## Problem Restatement

We are given an elevation map as an integer array `heights`.

The value `heights[i]` is the current height at index `i`. Each index has width `1`.

We are also given:

```python
volume
k
```

`volume` units of water fall at index `k`, one unit at a time.

Each unit of water follows these rules:

1. It first tries to move left.
2. If moving left can eventually make it fall to a lower level, it settles at the best left position.
3. Otherwise, it tries to move right.
4. If moving right can eventually make it fall to a lower level, it settles at the best right position.
5. Otherwise, it stays at index `k`.

The level at an index means terrain height plus water already stored there.

Return the final `heights` array after all water has fallen.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `heights`, an integer array |
| Input | `volume`, the number of water units |
| Input | `k`, the index where water falls |
| Output | The final height array after pouring all water |
| Rule | Each water unit occupies exactly one index |

Example function shape:

```python
def pourWater(heights: list[int], volume: int, k: int) -> list[int]:
    ...
```

## Examples

Example:

```python
heights = [2, 1, 1, 2, 1, 2, 2]
volume = 4
k = 3
```

Output:

```python
[2, 2, 2, 3, 2, 2, 2]
```

The first water unit falls at index `3`.

It tries to move left. Since it can eventually reach a lower level on the left, it settles at index `2`.

The second water unit also tries left first and settles at index `1`.

The third water unit cannot fall left anymore, so it tries right and settles at index `4`.

The fourth water unit cannot fall left or right, so it stays at index `3`.

Final result:

```python
[2, 2, 2, 3, 2, 2, 2]
```

## First Thought: Simulate the Water

This problem is a direct simulation.

The position of each new water unit depends on where previous water units settled.

So we process water one unit at a time.

For each unit, we decide where it settles, then increase that position by `1`.

## Key Insight

A droplet prefers the left side.

So for each water unit:

1. Search left from `k`.
2. If there is a lower reachable position, place the water at the leftmost best position.
3. Otherwise, search right from `k`.
4. If there is a lower reachable position, place the water at the right-side best position.
5. Otherwise, place it at `k`.

The phrase "eventually fall" matters.

A droplet can move across equal-height positions, but it only settles in a direction if it eventually finds a lower height.

For example:

```python
heights = [3, 2, 2, 2]
k = 3
```

From index `3`, the water can move left across equal levels and eventually reach height `2`, which is lower than height `3`.

So moving left is allowed.

## Finding the Left Position

Start at `k`.

Move left while the next position is not higher:

```python
while i > 0 and heights[i - 1] <= heights[i]:
    i -= 1
```

This lets the droplet move across flat or downward terrain.

After this scan, `i` is the leftmost reachable position before the path would need to climb.

But we only use this position if it is lower than the original index `k`.

```python
if heights[i] < heights[k]:
    heights[i] += 1
    continue
```

If this condition is true, the droplet eventually falls left and settles there.

## Finding the Right Position

If the droplet cannot fall left, we try the right side.

Start again at `k`.

Move right while the next position is not higher:

```python
while i + 1 < len(heights) and heights[i + 1] <= heights[i]:
    i += 1
```

Then we check whether this position is lower than `k`:

```python
if heights[i] < heights[k]:
    heights[i] += 1
    continue
```

If yes, the droplet settles there.

If not, it stays at `k`.

## Algorithm

1. Repeat `volume` times.
2. For each droplet:
   1. Set `i = k`.
   2. Move `i` left while the next left level is less than or equal to the current level.
   3. If `heights[i] < heights[k]`, add water at `i`.
   4. Otherwise, reset `i = k`.
   5. Move `i` right while the next right level is less than or equal to the current level.
   6. If `heights[i] < heights[k]`, add water at `i`.
   7. Otherwise, add water at `k`.
3. Return `heights`.

## Correctness

Each droplet is handled independently, and the array is updated immediately after the droplet settles. Therefore, when the next droplet is processed, it sees the correct current levels.

For the left search, the algorithm moves from `k` left while the droplet can move to a position of equal or lower level. This exactly matches the rule that the droplet may move left without climbing. If the search ends at a position whose level is lower than the level at `k`, then moving left eventually makes the droplet fall, so the droplet must choose that side.

If the droplet cannot eventually fall left, the problem rule says it should try right. The right search applies the same logic in the right direction. If it finds a lower reachable position, the droplet settles there.

If neither side provides a lower reachable position, the rules say the droplet rises at its current position, which is index `k`. The algorithm then increments `heights[k]`.

Since the algorithm applies the exact priority order for every droplet, and updates the level after each droplet, the final array is exactly the result of pouring all `volume` units of water.

## Complexity

Let `m = len(heights)`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(volume * m)` | Each droplet may scan left and right across the array |
| Space | `O(1)` | The array is modified in place |

## Implementation

```python
class Solution:
    def pourWater(self, heights: list[int], volume: int, k: int) -> list[int]:
        for _ in range(volume):
            i = k

            while i > 0 and heights[i - 1] <= heights[i]:
                i -= 1

            if heights[i] < heights[k]:
                heights[i] += 1
                continue

            i = k

            while i + 1 < len(heights) and heights[i + 1] <= heights[i]:
                i += 1

            if heights[i] < heights[k]:
                heights[i] += 1
                continue

            heights[k] += 1

        return heights
```

## Code Explanation

We process exactly one droplet per loop:

```python
for _ in range(volume):
```

For each droplet, we first search left:

```python
i = k

while i > 0 and heights[i - 1] <= heights[i]:
    i -= 1
```

The condition `heights[i - 1] <= heights[i]` means the droplet can move left without climbing.

After the scan, we check whether this left position is actually lower than the starting level:

```python
if heights[i] < heights[k]:
    heights[i] += 1
    continue
```

If so, the droplet settles there, and we move on to the next droplet.

If not, we search right:

```python
i = k

while i + 1 < len(heights) and heights[i + 1] <= heights[i]:
    i += 1
```

Again, the droplet may move across equal or lower levels.

If the final right position is lower than index `k`, the droplet settles there:

```python
if heights[i] < heights[k]:
    heights[i] += 1
    continue
```

If neither side works, the water stays at `k`:

```python
heights[k] += 1
```

## Testing

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

    assert s.pourWater([2, 1, 1, 2, 1, 2, 2], 4, 3) == [
        2, 2, 2, 3, 2, 2, 2
    ]

    assert s.pourWater([1, 2, 3, 4], 2, 2) == [
        2, 3, 3, 4
    ]

    assert s.pourWater([3, 1, 3], 5, 1) == [
        4, 4, 4
    ]

    assert s.pourWater([1, 1, 1], 3, 1) == [
        2, 2, 1
    ]

    assert s.pourWater([5], 3, 0) == [
        8
    ]

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Main example | Checks the standard left-first, then right behavior |
| Increasing slope | Water moves left before staying |
| Valley | Water fills the middle first, then sides |
| Flat terrain | Left preference matters |
| Single column | All water must stay at `k` |