Trapping Rainwater in Java | Two Pointers | Java Interview Prep: Advanced #04

Code & Test Automation |    / @codetestautomation   Learn how to solve Trapping Rain Water in Java in O(n) time and O(1) space with two pointers, a classic hard coding interview question! In this lesson we cover the contract (nonnegative heights, width 1 per position, return long), a real-life picture of rain filling the dips between walls, the simple prefix-maximum idea that needs O(n) extra space, the plan from the guide, the Java code line by line, a full dry run of [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] (answer 6), the [3, 0, 3] case where both walls are equal, edge cases such as empty and monotone heights, O(n) time and O(1) space, and the follow-up: why the side with the lower boundary can be finalized without scanning ahead. Episode 4 of 20 in Java Interview Prep: Advanced (advanced windows, monotonic structures, linked lists, trees, tries, dynamic programming, weighted graphs and backtracking). CHAPTERS 0:00 Introduction 0:52 The problem 1:43 Intuition 2:32 The simple idea 3:17 The plan 3:43 The Java code 4:38 Dry run 6:38 Equal walls 7:25 Edge cases & tests 8:23 Complexity 8:47 Interview follow-up 9:45 Recap 10:13 Subscribe THE SOLUTION (Java) static long trapRainWater(int[] h) { int left = 0, right = h.length - 1, leftMax = 0, rightMax = 0; long water = 0; while (left ‹= right) { if (h[left] ‹= h[right]) { leftMax = Math.max(leftMax, h[left]); water += leftMax - h[left++]; } else { rightMax = Math.max(rightMax, h[right]); water += rightMax - h[right--]; } } return water; } Example: trapRainWater([0,1,0,2,1,0,1,3,2,1,2,1]) =› 6 Complexity: O(n) time; O(1) auxiliary space. Practice tip: type it, run it, then explain it out loud: the invariant, the complexity and the edge cases. Next episode: #05 Median of two sorted arrays. #Java #CodingInterview #DSA #CodeAndTestAutomation Subscribe to Code & Test Automation for more Java interview prep:    / @codetestautomation