Interview 150
Trapping Rain Water
- Problem
- LC 42
- File
- interview150_LC42TrappingRainWater.java
- Path
- pkg5leetcode/interview150/interview150_LC42TrappingRainWater.java
- Package
- pkg5leetcode.interview150
- Command
- java pkg5leetcode/interview150/interview150_LC42TrappingRainWater.java
- Approach
- Two pointers track left/right max; accumulate trapped water.
- Complexity
- Time O(n), Space O(1)
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.interview150;2 3/*4 * Trapping Rain Water | LC 425 * APPROACH: Two pointers track left/right max; accumulate trapped water.6 * COMPLEXITY: Time O(n), Space O(1)7 */8public class interview150_LC42TrappingRainWater {9 static int trap(int[] height) {10 int l = 0, r = height.length - 1, lMax = 0, rMax = 0, water = 0;11 while (l < r) {12 if (height[l] < height[r]) {13 lMax = Math.max(lMax, height[l]);14 water += lMax - height[l];15 l++;16 } else {17 rMax = Math.max(rMax, height[r]);18 water += rMax - height[r];19 r--;20 }21 }22 return water;23 }24 25 public static void main(String[] args) {26 check(trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}) == 6, "case1");27 check(trap(new int[]{4, 2, 0, 3, 2, 5}) == 9, "case2");28 System.out.println("all tests passed");29 }30 31 static void check(boolean cond, String name) {32 if (!cond) throw new AssertionError("FAILED: " + name);33 System.out.println(" PASS " + name);34 }35}