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:

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

Example function shape:

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

Examples

Example:

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

Output:

[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:

[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:

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:

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.

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:

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

Then we check whether this position is lower than k:

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).

Implementation

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:

for _ in range(volume):

For each droplet, we first search left:

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:

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:

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:

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

If neither side works, the water stays at k:

heights[k] += 1

Testing

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: