Leetcode 755. Pour Water

Let's understand what we're being asked to do. We have an array of terrain heights like [3, 1, 2] and we pour V droplets one by one at index K.

Each droplet follows a greedy rule: it rolls to the leftmost lowest reachable position. If it can't roll left (blocked by higher terrain), it tries to roll right. If it can't roll either direction, it settles at the current position.

For example, if we have heights [3, 1, 2] and pour a droplet at index 1 (height 1): The droplet checks left - index 0 has height 3 (higher, can't roll left). It checks right - index 2 has height 2 (higher, can't roll right). So it settles at index 1, making the new heights [3, 2, 2].

Important constraint: Each droplet increases the height at its settling position by 1. This changes the terrain for subsequent droplets!

Edge cases to consider: What if a droplet can roll to multiple positions with the same height? (choose leftmost). What if the droplet is poured at the edge of the array? What if all positions are equally low?

Each droplet makes a local greedy decision: scan left first to find the lowest reachable position, then scan right if needed.

The key insight is that a droplet can only roll to adjacent positions that are lower or equal in height. Once it encounters a higher position, it's blocked in that direction.

By simulating each droplet's left-then-right scan, we naturally find the leftmost lowest position. The greedy rule means we don't need to consider all possible paths - just follow the local height comparisons.

After each droplet settles, updating the height at that position affects future droplets, creating a dynamic terrain that evolves with each pour.

Imagine pouring water on a staircase. The water flows downward (to lower steps) until it reaches a step where it can't flow further down.

If there are multiple equally low steps, the water naturally flows to the leftmost one first (due to left-to-right scanning). Once a step gets wet, it becomes slightly higher, affecting where the next drop of water will flow.

For each of the V droplets, simulate the greedy rolling process. Start at index K and scan left to find the leftmost position with the lowest reachable height. If no lower position exists to the left, scan right to find the lowest reachable position. Once the settling position is found, increment the height at that position by 1. Repeat this process for all V droplets, updating the terrain after each droplet settles.

def pour_water(heights, V, K):
    """
    Simulate V droplets poured at index K, each rolling greedily
    to the leftmost lowest reachable position (or right if no lower left).
    """
    n = len(heights)
    
    # Process each droplet one by one
    for drop in range(V):
        # Start at pour position K
        current_pos = K
        
        # Phase 1: Scan left for leftmost lowest position
        left_pos = K
        for i in range(K - 1, -1, -1):
            if heights[i] < heights[left_pos]:
                left_pos = i
            elif heights[i] > heights[left_pos]:
                break
        
        # If found lower position to the left, settle there
        if left_pos != K:
            heights[left_pos] += 1
            continue
        
        # Phase 2: Scan right for lowest position
        right_pos = K
        for i in range(K + 1, n):
            if heights[i] < heights[right_pos]:
                right_pos = i
            elif heights[i] > heights[right_pos]:
                break
        
        # Settle at the found position (could be K itself)
        heights[right_pos] += 1
    
    return heights

• Greedy simulation with directional priority: When simulating physical processes like water flow, implement a strict priority order (left-first, then right, then stay) by scanning in separate passes - this ensures each droplet follows the correct greedy decision path without complex backtracking logic.
• Local minimum search pattern: Use bounded linear scans to find the lowest reachable position within constraints - scan left from K while tracking the minimum height encountered, then repeat for right if no valid left position exists, ensuring you stop at the first barrier (upward slope).
• In-place height modification: Update the terrain array immediately after each droplet settles rather than batching updates - this is crucial because each subsequent droplet must see the accumulated changes from all previous droplets to simulate realistic stacking behavior.
• Strict inequality vs non-strict comparison: The critical bug trap is using `heights[i] < currentMin` (strict) when scanning to ensure water only flows downward, not onto equal-height positions - using `<=` causes water to slide horizontally indefinitely instead of settling at the first valid minimum.
• Three-way decision tree implementation: Structure your solution as three distinct checks: (1) find leftmost lower position, (2) if none exists, find rightmost lower position, (3) if neither exists, stay at K - this mirrors real physics where water explores all downhill options before settling.
• Iterative state evolution pattern: This problem exemplifies sequential state modification where each iteration depends on all previous iterations - recognize this pattern in problems involving gravity, cascading effects, or time-step simulations where order of operations fundamentally matters.