Pour Water
Pour Water is a medium arrays & hashing problem solved with the simulation pattern.
The best approach, optimal (one walk per side), runs in O(V · n) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (find the basin, then its lowest point) up.
Problem
You get an elevation map heights, where heights[i] is the height of the column at index i (each column has width 1). Then volume units of water are dropped, one at a time, onto index k. Each unit settles into a single column and raises it by 1, and the terrain is surrounded by walls of infinite height on both ends.
A unit lands on top of column k and moves as follows:
- If moving left would let it eventually reach a lower level, it moves left. It may only pass over columns that are not higher than where it currently is, and it settles at the lowest such position it can reach; if several positions tie, it takes the one nearest to
k. - Otherwise, if moving right would let it eventually reach a lower level, it does the same to the right.
- Otherwise it stays on column
k.
Return the heights after all the water has been poured.
Examples
Example 1
- Input
heights = [3, 1, 2, 2, 4, 0, 3], volume = 3, k = 3- Output
[3, 2, 3, 3, 4, 0, 3]- Why
- Unit 1 rolls left into the dip at index 1. Unit 2 finds nothing lower on the left and the 4 blocks the right, so it stays at index 3. Unit 3 now sees a lower column at index 2 and stops there, the nearest of the two equal lows.
Example 2
- Input
heights = [2, 1, 2], volume = 2, k = 1- Output
[2, 3, 2]- Why
- Both units are poured into the dip itself; neither side is lower, so they stack at index 1.
Example 3
- Input
heights = [1, 3, 1], volume = 3, k = 1- Output
[3, 3, 2]- Why
- Units 1 and 2 both roll left to index 0. After that the left side is level with index 1, so unit 3 goes right to index 2.
Constraints
1 <= heights.length <= 1000 <= heights[i] <= 990 <= volume <= 20000 <= k < heights.length
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (find the basin, then its lowest point) | O(V · n) | O(1) |
| Optimal (one walk per side) | O(V · n) | O(1) |
1Brute force (find the basin, then its lowest point)
O(V · n)Each of the V units does up to two passes over each side of the array.O(1)The heights array is updated in place.For each unit, first find how far it could roll to the left: from k, extend while the next column is not higher. Then scan that whole stretch for its minimum height, preferring the position closest to k. If that minimum is below heights[k], the unit settles there. Otherwise repeat on the right; if neither side is lower, the unit stays at k.
- Repeat volume times:
- Left: L = k; while L > 0 and heights[L - 1] <= heights[L], L--. Scan i from k down to L and remember the first index with the smallest height.
- If that height is below heights[k], add 1 there and continue with the next unit.
- Right: same with R moving up from k.
- Otherwise add 1 at k.
class Solution {
public int[] pourWater(int[] heights, int volume, int k) {
int n = heights.length;
for (int v = 0; v < volume; v++) {
int target = lowest(heights, k, -1);
if (target == k) target = lowest(heights, k, 1);
heights[target]++;
}
return heights;
}
// lowest reachable position on one side, or k if nothing there is lower than heights[k]
private int lowest(int[] h, int k, int d) {
int end = k;
while (end + d >= 0 && end + d < h.length && h[end + d] <= h[end]) end += d;
int best = k;
for (int i = k; i != end + d; i += d) {
if (h[i] < h[best]) best = i;
}
return best;
}
}class Solution:
def pourWater(self, heights: List[int], volume: int, k: int) -> List[int]:
h = heights
n = len(h)
def lowest(d: int) -> int:
end = k
while 0 <= end + d < n and h[end + d] <= h[end]:
end += d
best = k
i = k
while i != end + d:
if h[i] < h[best]:
best = i
i += d
return best
for _ in range(volume):
target = lowest(-1)
if target == k:
target = lowest(1)
h[target] += 1
return hclass Solution {
public:
vector<int> pourWater(vector<int>& heights, int volume, int k) {
for (int v = 0; v < volume; v++) {
int target = lowest(heights, k, -1);
if (target == k) target = lowest(heights, k, 1);
heights[target]++;
}
return heights;
}
private:
int lowest(vector<int>& h, int k, int d) {
int n = h.size();
int end = k;
while (end + d >= 0 && end + d < n && h[end + d] <= h[end]) end += d;
int best = k;
for (int i = k; i != end + d; i += d) {
if (h[i] < h[best]) best = i;
}
return best;
}
};function pourWater(heights, volume, k) {
const h = heights;
const n = h.length;
function lowest(d) {
let end = k;
while (end + d >= 0 && end + d < n && h[end + d] <= h[end]) end += d;
let best = k;
for (let i = k; i !== end + d; i += d) {
if (h[i] < h[best]) best = i;
}
return best;
}
for (let v = 0; v < volume; v++) {
let target = lowest(-1);
if (target === k) target = lowest(1);
h[target]++;
}
return h;
}2Optimal (one walk per side)
O(V · n)Each unit walks at most once to each side, which is at most n steps; this halves the work of the brute force but keeps the same bound.O(1)Only a few indices; the array is updated in place.Combine the two scans into one. While walking left from k over columns that are not higher, the height never increases, so the lowest point closest to k is the last spot where the height strictly dropped. Track that spot during the walk; if it moved away from k, the unit settles there. Otherwise do the same walk to the right, and fall back to k.
- Repeat volume times:
- For d in (-1, +1): i = best = k. While i + d is inside and heights[i + d] <= heights[i]: if heights[i + d] < heights[i], best = i + d; then i += d.
- If best != k after a side, add 1 at best and go to the next unit.
- If neither side moved best, add 1 at k.
class Solution {
public int[] pourWater(int[] heights, int volume, int k) {
int n = heights.length;
for (int v = 0; v < volume; v++) {
int target = k;
for (int d = -1; d <= 1 && target == k; d += 2) {
int i = k;
while (i + d >= 0 && i + d < n && heights[i + d] <= heights[i]) {
if (heights[i + d] < heights[i]) target = i + d;
i += d;
}
}
heights[target]++;
}
return heights;
}
}class Solution:
def pourWater(self, heights: List[int], volume: int, k: int) -> List[int]:
h = heights
n = len(h)
for _ in range(volume):
target = k
for d in (-1, 1):
i = k
while 0 <= i + d < n and h[i + d] <= h[i]:
if h[i + d] < h[i]:
target = i + d
i += d
if target != k:
break
h[target] += 1
return hclass Solution {
public:
vector<int> pourWater(vector<int>& heights, int volume, int k) {
int n = heights.size();
for (int v = 0; v < volume; v++) {
int target = k;
for (int d = -1; d <= 1 && target == k; d += 2) {
int i = k;
while (i + d >= 0 && i + d < n && heights[i + d] <= heights[i]) {
if (heights[i + d] < heights[i]) target = i + d;
i += d;
}
}
heights[target]++;
}
return heights;
}
};function pourWater(heights, volume, k) {
const n = heights.length;
for (let v = 0; v < volume; v++) {
let target = k;
for (let d = -1; d <= 1 && target === k; d += 2) {
let i = k;
while (i + d >= 0 && i + d < n && heights[i + d] <= heights[i]) {
if (heights[i + d] < heights[i]) target = i + d;
i += d;
}
}
heights[target]++;
}
return heights;
}Edge cases to test
volume = 0: return the heights unchanged- A single column: every unit stacks on it
- Flat ground: a unit cannot fall anywhere, so it stays at
k - A plateau next to
kthat leads down to a dip: the unit must walk across the plateau - Both sides lead lower: the left side always wins
- Several equally low positions on one side: take the one closest to
k
Hints
Hint 1
Handle the units one by one; each unit changes the terrain for the next.
Hint 2
From k, walk left while the next column is not higher than the current one. The unit settles at the lowest point of that walk, and among equal lows the one nearest k. If that point is not lower than heights[k], try the right side the same way.
Hint 3
In a non-increasing walk the lowest point closest to k is simply the last place where the height strictly dropped, so one pass per side is enough.
FAQ
What is the best time complexity for Pour Water?
Optimal (one walk per side) runs in O(V · n) time and O(1) extra space. Each unit walks at most once to each side, which is at most n steps; this halves the work of the brute force but keeps the same bound.
Which pattern does Pour Water use?
It is a arrays & hashing problem that uses the simulation pattern. Other problems with the same pattern: Text Justification, Integer to English Words, String to Integer (atoi).
Is there a brute force solution for Pour Water?
Yes. Brute force (find the basin, then its lowest point) takes O(V · n) time and O(1) space. For each unit, first find how far it could roll to the left: from k, extend while the next column is not higher.
Which edge cases should I test for Pour Water?
volume = 0: return the heights unchanged; A single column: every unit stacks on it; Flat ground: a unit cannot fall anywhere, so it stays at k; A plateau next to k that leads down to a dip: the unit must walk across the plateau; Both sides lead lower: the left side always wins; Several equally low positions on one side: take the one closest to k.