Limited Time Offer:Up to 25% off Hello Interview Premium

Your Dashboard

Interview Coaching

Mock Interviews

1:1 Mentorship

Salary Negotiation

Practice

Learn

System Design

ML System Design

Low Level Design

Code

Behavioral

Salary Negotiation

Interview Guides

Blog

Community

Interview Questions

Interview Experiences

Peer System Design Library

Ask The Community

Discord

Refer a Friend

Pricing

Become a Coach

⌘K

Pricing Become a Coach

⌘K

Tutor

Get Premium

Leetcode 755. Pour Water

Given an array of terrain heights, V droplets are poured one by one at index K and each droplet greedily rolls to the leftmost lowest reachable position (otherwise to the right) before settling; return the final heights after all drops. The core challenge is correctly simulating these local greedy flows (left-then-right scan) and updating heights efficiently.

Asked at:

Google

DESCRIPTION

Input:

heights = [3, 1, 2], V = 2, K = 1

Output:

[3, 3, 2]

Explanation: First droplet at index 1: can't roll left (3 > 1) or right (2 > 1), settles at index 1 → [3, 2, 2]. Second droplet at index 1: can't roll left (3 > 2) or right (2 = 2, but not lower), settles at index 1 → [3, 3, 2]

Constraints:

1 <= heights.length <= 100
0 <= heights[i] <= 100
1 <= V <= 1000
0 <= K < heights.length
Each droplet increases height by 1 at its settling position

Understanding the Problem

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?

Building Intuition

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.

Common Mistakes

Forgetting to prioritize left over right when both directions have equally low positions - the problem requires leftmost, not just any lowest position

Not updating the height immediately after each droplet settles - this causes incorrect terrain for subsequent droplets

Incorrectly handling edge cases where K is at index 0 or the last index - boundary checks are crucial to avoid out-of-bounds errors

Comparing heights incorrectly during scanning - a droplet can only roll to positions that are strictly lower, not equal (except when choosing between left and right)

Not resetting the search position to K for each new droplet - each droplet starts fresh at index K, not where the previous one settled

Optimal Solution

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.

Visualization

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

Start pouring water

0 / 20

Test Your Knowledge

Complexity Analysis

Time Complexity: O(V * n) For each of V droplets, we potentially scan the entire array of length n to find the settling position. In the worst case, each droplet requires a full left-to-right scan.

Space Complexity: O(1) We only modify the input array in-place and use a constant amount of extra space for tracking the current position and minimum height during scanning.

What We've Learned

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.

Test Your Understanding

Why is bars the right data structure for this problem?

bars provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Mid December, 2024

Google

Mid-level

Store the list of points where water would be collected in the matrix problem

Mid December, 2024

Google

Mid-level

Find the point where water gets stored in a matrix when water falls from each point, using graphs and DP

Mid December, 2024

Google

Mid-level

Find the point where water gets stored in a matrix when water falls from each point, using graphs and DP

Get Premium to View All 4 Reports

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

Leetcode 755. Pour Water

DESCRIPTION

Understanding the Problem

Building Intuition

Common Mistakes

Optimal Solution

Test Your Knowledge

Complexity Analysis

What We've Learned

Related Concepts and Problems to Practice

Test Your Understanding

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact