You are given an elevation map represents as an integer array heights where heights[i] representing the height of the terrain at index i. The width at each index is 1. You are also given two integers volume and k. volume units of water will fall at index k.
Water first drops at the index k and rests on top of the highest terrain or water at that index. Then, it flows according to the following rules:
Here, "eventually fall" means that the droplet will eventually be at a lower level if it moves in that direction. Also, level means the height of the terrain plus any water in that column.
We can assume there is infinitely high terrain on the two sides out of bounds of the array. Also, there could not be partial water being spread out evenly on more than one grid block, and each unit of water has to be in exactly one block.
Example 1:
Input: heights = [2,1,1,2,1,2,2], volume = 4, k = 3 Output: [2,2,2,3,2,2,2] Explanation: The first drop of water lands at index k = 3. When moving left or right, the water can only move to the same level or a lower level. (By level, we mean the total height of the terrain plus any water in that column.) Since moving left will eventually make it fall, it moves left. (A droplet "made to fall" means go to a lower height than it was at previously.) Since moving left will not make it fall, it stays in place.The next droplet falls at index k = 3. Since the new droplet moving left will eventually make it fall, it moves left. Notice that the droplet still preferred to move left, even though it could move right (and moving right makes it fall quicker.)
The third droplet falls at index k = 3. Since moving left would not eventually make it fall, it tries to move right. Since moving right would eventually make it fall, it moves right.
Finally, the fourth droplet falls at index k = 3. Since moving left would not eventually make it fall, it tries to move right. Since moving right would not eventually make it fall, it stays in place.
Example 2:
Input: heights = [1,2,3,4], volume = 2, k = 2 Output: [2,3,3,4] Explanation: The last droplet settles at index 1, since moving further left would not cause it to eventually fall to a lower height.
Example 3:
Input: heights = [3,1,3], volume = 5, k = 1 Output: [4,4,4]
Constraints:
1 <= heights.length <= 1000 <= heights[i] <= 990 <= volume <= 20000 <= k < heights.lengthProblem Overview: You’re given an array heights representing terrain elevation. Water is poured V times at index K. Each drop tries to flow left to the lowest possible position, otherwise right, and if neither side is lower it stays at K. The task is to simulate this process and return the final terrain heights.
Approach 1: Direct Simulation (O(V * n) time, O(1) space)
The problem is fundamentally a simulation. For every unit of water, start at index K and scan left to find the first position where water can settle. While scanning, track the lowest height encountered; water prefers the leftmost lowest point. If a valid position exists, increment its height and continue with the next drop.
If no lower position exists on the left, repeat the same scan to the right. Move right while the terrain does not increase, again remembering the lowest reachable point. If a lower position is found, place the water there. If both scans fail to find a lower position, the water settles at K. Each drop performs at most two linear scans of the array, giving O(n) work per drop.
This approach works because water always flows to the closest valley that is reachable without climbing over a higher wall. The simulation exactly mirrors the problem rules, which keeps the implementation simple and predictable.
Approach 2: Optimized Directional Simulation (O(V * n) time, O(1) space)
You can slightly optimize the simulation by keeping a pointer while scanning instead of repeatedly restarting comparisons. From K, walk left while the next cell is less than or equal to the current height, updating the best candidate index whenever a strictly lower height appears. If a placement position is found, increment it and move to the next drop immediately.
If the left search fails, repeat the process to the right. The directional walk avoids unnecessary backtracking and keeps comparisons minimal. Although the worst‑case complexity remains O(V * n), it performs well in practice and matches the typical editorial solution for this simulation problem.
Recommended for interviews: The directional simulation is what interviewers expect. It shows you can translate physical behavior into deterministic steps using an array scan. A naive idea like repeatedly redistributing water demonstrates understanding, but implementing the left-first valley search proves you can reason about edge conditions and flow rules efficiently.
We can simulate the process of each unit of water dropping. Each time a drop falls, we first try to move left. If it can move to a lower height, it moves to the lowest height; if it cannot move to a lower height, we try to move right. If it can move to a lower height, it moves to the lowest height; if it cannot move to a lower height, it rises at the current position.
The time complexity is O(v times n), and the space complexity is O(1), where v and n are the number of water drops and the length of the height array, respectively.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Simulation | O(V * n) | O(1) | Simple implementation when following the problem rules step‑by‑step |
| Optimized Directional Simulation | O(V * n) | O(1) | Preferred interview solution with cleaner valley search logic |
花花酱 LeetCode 755. Pour Water - 刷题找工作 EP151 • Hua Hua • 4,477 views views
Watch 5 more video solutions →Practice Pour Water with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor