Leetcode #755: Pour Water
In this guide, we solve Leetcode #755 Pour Water in Python and focus on the core idea that makes the solution efficient.
You will see the intuition, the step-by-step method, and a clean Python implementation you can use in interviews.
Problem Statement
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.
Quick Facts
- Difficulty: Medium
- Premium: Yes
- Tags: Array, Simulation
Intuition
The rules are explicit, so simulating the process step by step is safest.
Careful state updates prevent subtle bugs.
Approach
Translate the rules into state updates and apply them in order.
Track the final state or aggregate as required.
Steps:
- Translate rules into state updates.
- Iterate for each step.
- Return the final state.
Example
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.
Python Solution
class Solution:
def pourWater(self, heights: List[int], volume: int, k: int) -> List[int]:
for _ in range(volume):
for d in (-1, 1):
i = j = k
while 0 <= i + d < len(heights) and heights[i + d] <= heights[i]:
if heights[i + d] < heights[i]:
j = i + d
i += d
if j != k:
heights[j] += 1
break
else:
heights[k] += 1
return heights
Complexity
The time complexity is , and the space complexity is , where and are the number of water drops and the length of the height array, respectively. The space complexity is , where and are the number of water drops and the length of the height array, respectively.
Edge Cases and Pitfalls
Watch for boundary values, empty inputs, and duplicate values where applicable. If the problem involves ordering or constraints, confirm the invariant is preserved at every step.
Summary
This Python solution focuses on the essential structure of the problem and keeps the implementation interview-friendly while meeting the constraints.