The Question
CodingTrapping Rain Water
Given an array of $n$ non-negative integers representing an elevation map where the width of each bar is 1, calculate the total volume of water it can trap after a rainstorm.
Example:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The elevation map is represented by the array. In this case, 6 units of rain water are being trapped.
Constraints:
- $n == height.length$
- $1 \le n \le 2 \times 10^4$
- $0 \le height[i] \le 10^5$
Java
Two-Pointer Technique
Questions & Insights
Clarifying Questions
Input Size: What is the maximum possible size of the elevation map array (n)?
Value Range: What is the maximum possible height of an individual bar? This helps determine if the total volume might overflow a 32-bit
int.Edge Cases: How should we handle null inputs, empty arrays, or arrays with fewer than 3 elements (where trapping water is impossible)?
Memory Constraints: Is there a preference between a solution that uses O(n) space for clarity (like Dynamic Programming) versus O(1) space for optimization (Two-Pointer)?
Assumptions:
n is up to 10^5, and individual heights are non-negative.
The total trapped water will fit within a 32-bit signed integer.
If the array is null or has fewer than 3 elements, the result should be 0.
Thinking Process
Core Logic: The amount of water trapped at any index is determined by the "limiting factor" of the barriers on its sides. Specifically, it is
min(max_height_to_left, max_height_to_right) - height[i]. If this value is negative, no water is trapped at that index.Dynamic Programming Approach: We could pre-calculate two arrays,
leftMax and rightMax, where leftMax[i] stores the tallest bar from the start to i, and rightMax[i] stores the tallest bar from i to the end. This takes O(n) time and O(n) space.Optimizing Space (Two Pointers): We can optimize the space to O(1) using two pointers. Since the water trapped at a position only depends on the smaller of the two surrounding peaks, if we know
leftMax is smaller than the current rightMax, we can confidently calculate the water at the left pointer based on leftMax, regardless of any taller bars that might exist further to the right.Algorithm Execution: Maintain
left and right pointers and track leftMax and rightMax. Move the pointer pointing to the smaller height, update the corresponding max, and add the difference between that max and the current height to the total sum.Implementation Breakdown
Problem Set
Functional Requirements: Compute the total volume of water trapped between bars.
Constraints:
Time Complexity: O(n)
Space Complexity: O(1) preferred.
Input:
int[] height (non-negative).Approach
Algorithm: Two-Pointer Technique.
Data Structure: Array (Input).
Complexity:
Time: O(n) – Single pass through the array.
Space: O(1) – Only a few auxiliary variables used.
Implementation
Wrap Up
Advanced Topics
Monotonic Stack Approach: Alternatively, a stack-based approach can be used to solve this problem. We store indices in a stack such that heights are in decreasing order. When we find a bar taller than the stack's top, we have found a "valley" and can calculate trapped water horizontally. This is also O(n) time and O(n) space.
Parallelization: For extremely large datasets (billions of entries), the map can be partitioned. Each partition calculates its local water and exports the highest peaks at its boundaries. A secondary pass merges these peaks to resolve water trapped across partition boundaries.
Readability vs. Performance: While the two-pointer solution is O(1) space, the Dynamic Programming solution (O(n) space) is often considered more readable and easier to explain in an initial interview phase before optimizing.