LeetCode Problem 755

Difficulty: 🟡 Medium
Topics: Array, Simulation

Solution

LeetCode 755 - Pour Water

Problem Understanding

This problem asks us to simulate how water droplets behave when poured onto a one-dimensional terrain. The terrain is represented by the array heights, where each element describes the height of a column at that position.

We are also given:

• volume, the number of water droplets to pour
• k, the index where every droplet initially lands

Each droplet behaves independently and follows a strict movement rule before settling.

The droplet starts at index k. From there:

1. It first attempts to move left.
2. If moving left can eventually lead to a lower height, it keeps moving left.
3. If left does not work, it then attempts to move right.
4. If neither direction leads to a lower position, it stays at its current location.

The key detail is the phrase "eventually fall". A droplet is allowed to move across flat terrain while searching for a lower location. It does not stop immediately at the first equal-height position. Instead, it keeps exploring until it either finds a lower level or encounters a higher barrier.

The "level" at a position means:

terrain height + accumulated water

Since water accumulates over time, the effective heights change after every droplet settles.

The output is the final state of the heights array after all droplets have been poured. The modified array implicitly includes the water because each settled droplet increments the height at its resting position.

The constraints are relatively small:

• heights.length <= 100
• volume <= 2000

These limits strongly suggest that direct simulation is acceptable. We do not need advanced optimization techniques or sophisticated data structures. A careful simulation with nested loops will run comfortably within limits.

Several edge cases are important:

• Completely flat terrain
• Strictly increasing or decreasing terrain
• Multiple equal-height valleys
• Water trapped between walls
• Cases where water repeatedly settles at the source index
• Cases where the droplet can travel across equal heights before falling

A naive implementation can easily fail if it stops movement too early or does not correctly prioritize left movement over right movement.

Approaches

Brute Force Approach

The brute-force idea is to simulate every possible movement for every droplet in an extremely literal way.

For each droplet:

1. Start at index k
2. Repeatedly try moving left one step at a time
3. If a lower position is discovered, continue there
4. Otherwise restart from k and try the same process on the right side
5. Finally settle the droplet

This approach is correct because it exactly follows the movement rules from the problem statement. Every droplet independently searches for a valid resting position.

However, a poorly implemented brute-force solution may repeatedly scan large portions of the array unnecessarily. If we restart searches too often or simulate movement inefficiently, we can end up with redundant work.

Even though the constraints are small enough that many brute-force implementations pass, we can still organize the simulation more cleanly and efficiently.

Optimal Simulation Approach

The key observation is that a droplet always settles at the best reachable position according to the movement priority:

1. Furthest valid left descent
2. Otherwise furthest valid right descent
3. Otherwise current position

Instead of simulating the droplet cell by cell with complicated state tracking, we can directly search for the best resting location.

For the left search:

• Move left while heights do not increase
• Track the lowest position encountered
• If multiple positions have the same minimum height, choose the leftmost one

If no valid lower left position exists, perform the symmetric search on the right side.

This works because the droplet only cares about eventually reaching a lower level, not about the exact physical path.

The implementation becomes much cleaner:

• Scan left to find the best left resting point
• If found, place water there
• Otherwise scan right
• Otherwise place water at k

Since the array size is very small, this direct simulation is both efficient and easy to reason about.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(volume × n²)	O(1)	Simulates movement very literally with redundant rescanning
Optimal	O(volume × n)	O(1)	Efficient directional scans find the correct resting position directly

Algorithm Walkthrough

1. Initialize the simulation using the given heights array.

The array itself will store both terrain and accumulated water. Every time a droplet settles, we increment the height at that position. 2. Process each water droplet independently.

Since every droplet changes the terrain for future droplets, we must simulate them sequentially. 3. Attempt to move left first.

Start from index k and scan toward the left while the terrain does not increase.

Specifically, continue moving left while:

heights[i - 1] <= heights[i]

During this scan, track the position with the minimum height encountered. 4. If a lower left position exists, settle the droplet there.

The droplet prefers the leftmost valid descent. Once we identify the best left position, increment its height and move to the next droplet. 5. If left movement fails, attempt the same process on the right side.

Scan right while terrain does not increase:

heights[i + 1] <= heights[i]

Again, track the position with the minimum height encountered. 6. If a lower right position exists, settle the droplet there.

Increment the height at the chosen position. 7. If neither direction produces a lower position, settle at k.

This means the droplet cannot eventually fall in either direction. 8. Repeat until all droplets are processed. 9. Return the modified heights array.

Why it works

The algorithm works because it exactly mirrors the movement priorities defined in the problem statement.

A droplet only moves through positions that are not higher than its current level. While traversing such positions, it searches for a strictly lower level. The left search is always performed first, which preserves the required priority rule.

Tracking the minimum reachable height guarantees that the droplet settles at the correct final location. Since every droplet updates the terrain immediately, future droplets see the correct effective heights.

Python Solution

from typing import List

class Solution:
    def pourWater(self, heights: List[int], volume: int, k: int) -> List[int]:
        n = len(heights)

        for _ in range(volume):
            position = k

            # Try moving left
            best = k
            i = k

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

            if best != k:
                heights[best] += 1
                continue

            # Try moving right
            best = k
            i = k

            while i < n - 1 and heights[i + 1] <= heights[i]:
                if heights[i + 1] < heights[best]:
                    best = i + 1
                i += 1

            if best != k:
                heights[best] += 1
                continue

            # Stay at k
            heights[k] += 1

        return heights

The implementation directly follows the algorithm structure.

The outer loop processes each water droplet independently. Since the terrain changes after every droplet, sequential simulation is required.

The left scan begins at k and moves while the next position is not higher. During the traversal, the algorithm keeps track of the lowest reachable position. If a lower position is found, the droplet settles there immediately because left movement has higher priority than right movement.

If the left search fails, the algorithm performs the same logic on the right side.

Finally, if neither direction contains a lower reachable level, the droplet settles at the original index k.

The solution modifies the heights array in place, which naturally represents both terrain and accumulated water.

Go Solution

func pourWater(heights []int, volume int, k int) []int {
	n := len(heights)

	for v := 0; v < volume; v++ {

		// Try moving left
		best := k
		i := k

		for i > 0 && heights[i-1] <= heights[i] {
			if heights[i-1] < heights[best] {
				best = i - 1
			}
			i--
		}

		if best != k {
			heights[best]++
			continue
		}

		// Try moving right
		best = k
		i = k

		for i < n-1 && heights[i+1] <= heights[i] {
			if heights[i+1] < heights[best] {
				best = i + 1
			}
			i++
		}

		if best != k {
			heights[best]++
			continue
		}

		// Stay at k
		heights[k]++
	}

	return heights
}

The Go implementation mirrors the Python logic almost exactly.

Go slices are reference types, so modifying heights directly updates the underlying array. No additional copying is necessary.

Integer overflow is not a concern because the constraints are very small. The maximum possible height after all water is added remains well within Go's integer range.

The implementation uses iterative loops rather than recursion, so there are no stack depth concerns.

Worked Examples

Example 1

Input:

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

Initial state:

Index	0	1	2	3	4	5	6
Height	2	1	1	2	1	2	2

Droplet 1

Left scan from index 3:

2 -> 1 -> 1

Lowest reachable position is index 1.

Updated heights:

[2,2,1,2,1,2,2]

Droplet 2

Left scan again:

2 -> 1

Lowest reachable position is index 2.

Updated heights:

[2,2,2,2,1,2,2]

Droplet 3

Left side no longer contains a lower level.

Right scan:

2 -> 1

Lowest reachable position is index 4.

Updated heights:

[2,2,2,2,2,2,2]

Droplet 4

Neither left nor right contains a lower level.

Water settles at index 3.

Final result:

[2,2,2,3,2,2,2]

Example 2

Input:

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

Initial state:

[1,2,3,4]

Droplet 1

Left scan finds index 0 as the lowest reachable position.

Updated heights:

[2,2,3,4]

Droplet 2

Left scan reaches:

2 -> 2

No lower position exists.

Water settles at index 1.

Final result:

[2,3,3,4]

Example 3

Input:

heights = [3,1,3]
volume = 5
k = 1

Initial state:

[3,1,3]

Droplets repeatedly settle at the center until heights equalize.

State progression:

Droplet	Heights
1	[3,2,3]
2	[3,3,3]
3	[4,3,3]
4	[4,3,4]
5	[4,4,4]

Final result:

[4,4,4]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(volume × n)	Each droplet may scan across the array once to the left and once to the right
Space	O(1)	Only a few variables are used besides the input array

The algorithm processes each droplet independently. For every droplet, the left and right scans each take at most O(n) time. Since there are volume droplets, the total complexity becomes O(volume × n).

The solution is space efficient because all updates happen directly inside the input array without additional data structures.

Test Cases

from typing import List

class Solution:
    def pourWater(self, heights: List[int], volume: int, k: int) -> List[int]:
        n = len(heights)

        for _ in range(volume):
            best = k
            i = k

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

            if best != k:
                heights[best] += 1
                continue

            best = k
            i = k

            while i < n - 1 and heights[i + 1] <= heights[i]:
                if heights[i + 1] < heights[best]:
                    best = i + 1
                i += 1

            if best != k:
                heights[best] += 1
                continue

            heights[k] += 1

        return heights

sol = Solution()

assert sol.pourWater([2,1,1,2,1,2,2], 4, 3) == [2,2,2,3,2,2,2]  # official example 1

assert sol.pourWater([1,2,3,4], 2, 2) == [2,3,3,4]  # official example 2

assert sol.pourWater([3,1,3], 5, 1) == [4,4,4]  # official example 3

assert sol.pourWater([1], 5, 0) == [6]  # single element array

assert sol.pourWater([1,1,1,1], 2, 2) == [2,2,1,1]  # flat terrain prefers left

assert sol.pourWater([5,4,3,2,1], 3, 4) == [5,4,3,2,4]  # strictly decreasing terrain

assert sol.pourWater([1,2,3,4,5], 3, 0) == [4,2,3,4,5]  # strictly increasing terrain

assert sol.pourWater([2,1,2], 1, 1) == [2,2,2]  # valley fills directly

assert sol.pourWater([2,2,2], 3, 1) == [3,3,2]  # equal heights with left priority

assert sol.pourWater([0,1,0,1,0], 4, 2) == [1,1,2,1,1]  # multiple valleys

assert sol.pourWater([10,1,10], 20, 1) == [10,21,10]  # large volume trapped in center

Test	Why
[2,1,1,2,1,2,2]	Validates official simulation behavior
[1,2,3,4]	Tests movement across increasing terrain
[3,1,3]	Tests trapped water accumulation
[1]	Smallest possible array
[1,1,1,1]	Verifies left preference on flat terrain
[5,4,3,2,1]	Tests strictly decreasing terrain
[1,2,3,4,5]	Tests strictly increasing terrain
[2,1,2]	Tests simple valley filling
[2,2,2]	Verifies equal-height traversal logic
[0,1,0,1,0]	Tests multiple valleys and balancing
[10,1,10]	Tests repeated accumulation in a trapped basin

Edge Cases

Completely Flat Terrain

A flat terrain such as:

[2,2,2,2]

can easily expose bugs in movement logic. A naive implementation may incorrectly allow the droplet to drift indefinitely or choose the wrong direction.

The problem specifies that left movement is preferred whenever possible. Our implementation correctly handles this by always scanning left first and only scanning right if no lower left position exists.

Deep Valley Between Tall Walls

Consider:

[10,1,10]

Water repeatedly settles in the center because neither side offers a lower reachable level. Some incorrect solutions attempt to spread water evenly or simulate fluid balancing, which is not allowed in this problem.

Our implementation treats each droplet independently and increments exactly one column per droplet, matching the problem requirements precisely.

Movement Across Equal Heights

A subtle case is:

[3,2,2,3]

A droplet may need to travel across equal heights before eventually falling lower. Incorrect implementations often stop as soon as they encounter an equal-height position.

Our scanning condition:

heights[next] <= heights[current]

allows traversal across flat regions while still searching for a lower position, which correctly implements the "eventually fall" rule.