DSA-017 · FOCUSED PRACTICE
Trapping Rain Water
Advanced · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 21850 deterministic checks. Learner drafts are not executed.
Understand the problem
Compute the total rain-water volume retained above a one-dimensional elevation profile of unit-width bars.
- height is non-null with 0–100,000 nonnegative int heights, each at most Integer.MAX_VALUE. Negative heights are outside the contract. Preserve the array.
- Return a long volume. At index i, water equals min(max(height[0..i]),max(height[i..n-1]))-height[i]. Empty, singleton, and two-bar inputs hold zero water.
- Bars have unit width. Sum water over all cells; this is not the maximum area between two bars. The maximum permitted volume fits in long, although it may exceed int.
Examples
Input:
[4,2,0,3,2,5]
Output:9Per-index volumes are [0,2,4,1,2,0].
Input:
[3,0,3]
Output:3The middle unit-width cell holds three units.
Before you start
- Array indexing and inclusive pointer bounds
- Loop invariants and Java value versus reference semantics
Recognize the structure
Water is limited by the lower enclosing maximum on its two sides. Prefix/suffix tables reveal the formula; two pointers remove those tables by finalizing the side whose established maximum is lower.
Your Java attempt
Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.
Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.
No unsaved text changes · 81/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.
Try before revealing
Hint 1
Write the per-index formula using left and right maxima.
Hint 2
If an established left wall is lower than an established right wall, which side can be finalized?
Hint 3
Process the smaller established maximum, update it, and add its difference from the chosen bar.
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Prefix and suffix maxima
Build inclusive prefix and suffix maxima, then sum min(prefix[i],suffix[i])-height[i]. For [3,0,2], prefix=[3,3,3] and suffix=[3,2,2], giving [0,2,0] and total 2. It takes O(n) time and O(n) auxiliary space; unlike repeated scanning, the bound at each cell is available in O(1).
Improve the baseline
Keep two established walls
leftMax is the maximum strictly before left; rightMax is the maximum strictly after right. Start both at zero, valid for nonnegative heights, with every cell unprocessed.
Finalize the smaller side
When leftMax<=rightMax, process height[left]: update leftMax and add leftMax-height[left]. If this bar is below the old left wall, an established right wall is at least as high. If it is a new record, it holds zero water itself.
Use the symmetric right rule
Otherwise update rightMax, add rightMax-height[right], and decrement right. Continue until the unprocessed interval is empty; every cell is finalized exactly once.
Why it is correct
Boundary invariant
At each iteration leftMax=max(0,height[0..left-1]) and rightMax=max(0,height[right+1..n-1]). water is the exact sum for processed cells; [left,right] is still unprocessed.
Why the chosen side is final
If leftMax<=rightMax and height[left]<=leftMax, the true right maximum is at least rightMax and the true left maximum is leftMax, so that cell holds leftMax-height[left]. If height[left]>leftMax, it is the inclusive left maximum and holds zero regardless of the unknown opposite interior. Updating the maximum gives the same expression in both cases. The right case is symmetric.
Exhaustion
Exactly one endpoint advances each iteration. The established walls remain accurate, all added volumes are nonnegative, and after n iterations no cell remains. Hence the accumulated long equals the specified per-cell sum.
Complete Java reference and baseline
Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.
public final class Solution {
public static long trap(int[] height) {
int left = 0, right = height.length - 1, leftMax = 0, rightMax = 0;
long water = 0;
while (left <= right) {
if (leftMax <= rightMax) {
leftMax = Math.max(leftMax, height[left]);
water += (long) leftMax - height[left];
left++;
} else {
rightMax = Math.max(rightMax, height[right]);
water += (long) rightMax - height[right];
right--;
}
}
return water;
}
public static long baseline(int[] height) {
int n = height.length;
if (n == 0) return 0;
int[] prefix = new int[n], suffix = new int[n];
prefix[0] = height[0]; suffix[n - 1] = height[n - 1];
for (int i = 1; i < n; i++) prefix[i] = Math.max(prefix[i - 1], height[i]);
for (int i = n - 2; i >= 0; i--) suffix[i] = Math.max(suffix[i + 1], height[i]);
long water = 0;
for (int i = 0; i < n; i++) water += (long) Math.min(prefix[i], suffix[i]) - height[i];
return water;
}
}
Read the meaningful blocks
Compare maxima, not partial totals
This version chooses using leftMax and rightMax before reading the chosen endpoint. Keep its proof with these exact state definitions.
Update before subtracting
A new record bar must contribute zero, not a negative amount.
Accumulate into long
Even two maximum-height walls around two zeros hold 4294967294 units. Each individual difference and the full sum are safe in long.
Complexity
O(n) time because exactly n cells are processed. O(1) auxiliary space, with no output array and no mutation.
The prefix/suffix baseline is O(n) time and O(n) space. An independent oracle rescans both sides per cell in O(n²), restricted to small generated tests; the large boundary-volume test uses its closed-form answer.
Exact-state walkthroughs
Reveal normal and boundary traces
Finalize cells against established walls
Input: [4,2,0,3,2,5] · Result: 9
Step 1 of 8: Begin with no established walls and no finalized cells.
leftMax and rightMax describe the processed exterior only.
- 0: 4
- 1: 2
- 2: 0
- 3: 3
- 4: 2
- 5: 5
| Variable | Value |
|---|---|
| values | [4,2,0,3,2,5] |
| left | 0 |
| right | 5 |
| leftMax | 0 |
| rightMax | 0 |
| water | 0 |
See the affected Java block
1 public final class Solution { 2 public static long trap(int[] height) { 3 int left = 0, right = height.length - 1, leftMax = 0, rightMax = 0; 4 long water = 0; 5 while (left <= right) { 6 if (leftMax <= rightMax) { 7 leftMax = Math.max(leftMax, height[left]); 8 water += (long) leftMax - height[left]; 9 left++; 10 } else { 11 rightMax = Math.max(rightMax, height[right]); 12 water += (long) rightMax - height[right]; 13 right--; 14 } 15 } 16 return water; 17 } 18 public static long baseline(int[] height) { 19 int n = height.length; 20 if (n == 0) return 0; 21 int[] prefix = new int[n], suffix = new int[n]; 22 prefix[0] = height[0]; suffix[n - 1] = height[n - 1]; 23 for (int i = 1; i < n; i++) prefix[i] = Math.max(prefix[i - 1], height[i]); 24 for (int i = n - 2; i >= 0; i--) suffix[i] = Math.max(suffix[i + 1], height[i]); 25 long water = 0; 26 for (int i = 0; i < n; i++) water += (long) Math.min(prefix[i], suffix[i]) - height[i]; 27 return water; 28 } 29 } 30
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Begin with no established walls and no finalized cells.
leftMax and rightMax describe the processed exterior only.
- values
[4,2,0,3,2,5]- left
0- right
5- leftMax
0- rightMax
0- water
0
- Finalize the left cell using established boundary maxima.
A bar below the chosen old maximum has a sufficient opposite wall; a new record holds zero water itself.
- values
[4,2,0,3,2,5]- left
1- right
5- leftMax
4- rightMax
0- water
0- index
0- added
0- side
"left"
- Finalize the right cell using established boundary maxima.
A bar below the chosen old maximum has a sufficient opposite wall; a new record holds zero water itself.
- values
[4,2,0,3,2,5]- left
1- right
4- leftMax
4- rightMax
5- water
0- index
5- added
0- side
"right"
- Finalize the left cell using established boundary maxima.
A bar below the chosen old maximum has a sufficient opposite wall; a new record holds zero water itself.
- values
[4,2,0,3,2,5]- left
2- right
4- leftMax
4- rightMax
5- water
2- index
1- added
2- side
"left"
- Finalize the left cell using established boundary maxima.
A bar below the chosen old maximum has a sufficient opposite wall; a new record holds zero water itself.
- values
[4,2,0,3,2,5]- left
3- right
4- leftMax
4- rightMax
5- water
6- index
2- added
4- side
"left"
- Finalize the left cell using established boundary maxima.
A bar below the chosen old maximum has a sufficient opposite wall; a new record holds zero water itself.
- values
[4,2,0,3,2,5]- left
4- right
4- leftMax
4- rightMax
5- water
7- index
3- added
1- side
"left"
- Finalize the left cell using established boundary maxima.
A bar below the chosen old maximum has a sufficient opposite wall; a new record holds zero water itself.
- values
[4,2,0,3,2,5]- left
5- right
4- leftMax
4- rightMax
5- water
9- index
4- added
2- side
"left"
- Return the contract result.
All required values have been finalized under the declared contract.
- result
9
Monotone terrain has no basin
Input: [1,2,3] · Result: 0
Step 1 of 5: Begin with no established walls and no finalized cells.
leftMax and rightMax describe the processed exterior only.
- 0: 1
- 1: 2
- 2: 3
| Variable | Value |
|---|---|
| values | [1,2,3] |
| left | 0 |
| right | 2 |
| leftMax | 0 |
| rightMax | 0 |
| water | 0 |
See the affected Java block
1 public final class Solution { 2 public static long trap(int[] height) { 3 int left = 0, right = height.length - 1, leftMax = 0, rightMax = 0; 4 long water = 0; 5 while (left <= right) { 6 if (leftMax <= rightMax) { 7 leftMax = Math.max(leftMax, height[left]); 8 water += (long) leftMax - height[left]; 9 left++; 10 } else { 11 rightMax = Math.max(rightMax, height[right]); 12 water += (long) rightMax - height[right]; 13 right--; 14 } 15 } 16 return water; 17 } 18 public static long baseline(int[] height) { 19 int n = height.length; 20 if (n == 0) return 0; 21 int[] prefix = new int[n], suffix = new int[n]; 22 prefix[0] = height[0]; suffix[n - 1] = height[n - 1]; 23 for (int i = 1; i < n; i++) prefix[i] = Math.max(prefix[i - 1], height[i]); 24 for (int i = n - 2; i >= 0; i--) suffix[i] = Math.max(suffix[i + 1], height[i]); 25 long water = 0; 26 for (int i = 0; i < n; i++) water += (long) Math.min(prefix[i], suffix[i]) - height[i]; 27 return water; 28 } 29 } 30
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Begin with no established walls and no finalized cells.
leftMax and rightMax describe the processed exterior only.
- values
[1,2,3]- left
0- right
2- leftMax
0- rightMax
0- water
0
- Finalize the left cell using established boundary maxima.
A bar below the chosen old maximum has a sufficient opposite wall; a new record holds zero water itself.
- values
[1,2,3]- left
1- right
2- leftMax
1- rightMax
0- water
0- index
0- added
0- side
"left"
- Finalize the right cell using established boundary maxima.
A bar below the chosen old maximum has a sufficient opposite wall; a new record holds zero water itself.
- values
[1,2,3]- left
1- right
1- leftMax
1- rightMax
3- water
0- index
2- added
0- side
"right"
- Finalize the left cell using established boundary maxima.
A bar below the chosen old maximum has a sufficient opposite wall; a new record holds zero water itself.
- values
[1,2,3]- left
2- right
1- leftMax
2- rightMax
3- water
0- index
1- added
0- side
"left"
- Return the contract result.
All required values have been finalized under the declared contract.
- result
0
Test the contract
Input:
[]
Output:0No cells.
Input:
[1,2,3]
Output:0Monotone terrain has no basin.
Input:
[3,0,3]
Output:3A single basin cell.
Input:
[2147483647,0,0,2147483647]
Output:4294967294Wide total volume.
Common mistakes and counterexamples
Confuse water with container area
Counterexample: [3,0,3] has water 3 but a maximum container area of 6.
Sum unit-width per-cell depths.
Subtract before updating a maximum
Counterexample: The first bar of [4] must add zero, not -4.
Update the chosen maximum first.
Accumulate in int
Counterexample: [2147483647,0,0,2147483647] holds 4294967294.
Use long water and widen arithmetic.
Follow-ups
Use a monotonic stack.
Store indices of decreasing bars. When a higher bar arrives, a popped bottom and remaining left boundary define a bounded layer with width right-left-1. Avoid double-counting layers; the stack uses O(n) storage.
Extend to a 2D map.
Two endpoints no longer describe the boundary. A minimum-boundary priority queue can expand inward from the perimeter; each cell’s escape boundary depends on paths, not just row or column maxima.
Return depths instead of a sum.
Store the finalized per-cell depths in an output array. This adds O(n) output space but preserves O(1) other workspace and the same side-finalization proof.