Trapping Rain Water
Calculate the total water trapped between elevation bars after rain. Given an elevation map represented as an array of bar heights, determine how much water can be trapped. This classic problem has an elegant O(n) time, O(1) space solution using two pointers. The key insight: water level at any position is determined by the minimum of maximum heights on both sides.
Visualization
Interactive visualization for Trapping Rain Water
Trapping Rain Water
• Time: O(n)
• Uses left/right max arrays
• Classic array problem
Interactive visualization with step-by-step execution
Implementation
1function trap(height: number[]): number {
2 if (!height.length) return 0;
3
4 let left = 0, right = height.length - 1;
5 let leftMax = 0, rightMax = 0;
6 let water = 0;
7
8 while (left < right) {
9 if (height[left] < height[right]) {
10 if (height[left] >= leftMax) {
11 leftMax = height[left];
12 } else {
13 water += leftMax - height[left];
14 }
15 left++;
16 } else {
17 if (height[right] >= rightMax) {
18 rightMax = height[right];
19 } else {
20 water += rightMax - height[right];
21 }
22 right--;
23 }
24 }
25
26 return water;
27}Deep Dive
Theoretical Foundation
Water trapped at position i = min(max_left, max_right) - height[i]. Three approaches: (1) Brute force O(n²): for each position, scan left and right for max. (2) Dynamic Programming O(n) time, O(n) space: precompute leftMax[] and rightMax[] arrays. (3) Two Pointers O(n) time, O(1) space: maintain leftMax and rightMax while moving pointers inward. The two-pointer approach works because we only need to know if leftMax < rightMax to decide which side limits water at current position. Move the pointer with smaller max height.
Complexity
Time
O(n)
O(n)
O(n)
Space
O(1)
Applications
Industry Use
Water management and reservoir design
Urban planning (drainage systems)
Game development (water physics)
Architectural planning
Terrain analysis in GIS
Graphics rendering (water simulation)
Use Cases
Related Algorithms
Binary Search Tree (BST)
A hierarchical data structure where each node has at most two children, maintaining the property that all values in the left subtree are less than the node's value, and all values in the right subtree are greater. This ordering property enables efficient O(log n) operations on average for search, insert, and delete. BSTs form the foundation for many advanced tree structures and are fundamental in computer science.
Stack
LIFO (Last-In-First-Out) data structure with O(1) push/pop operations. Stack is a fundamental linear data structure where elements are added and removed from the same end (top). It's essential for function calls, expression evaluation, backtracking algorithms, and undo operations in applications.
Queue
FIFO (First-In-First-Out) data structure with O(1) enqueue/dequeue operations. Queue is a fundamental linear data structure where elements are added at one end (rear) and removed from the other end (front). Essential for breadth-first search, task scheduling, and buffering systems.
Hash Table (Hash Map)
A data structure that implements an associative array abstract data type, mapping keys to values using a hash function. Hash tables provide O(1) average-case time complexity for insertions, deletions, and lookups, making them one of the most efficient data structures for key-value storage. The hash function computes an index into an array of buckets from which the desired value can be found.