Intermediate LevelData Structures & Algorithms
How do you solve the Trapping Rain Water problem optimally?
ā Interview Prompt: Solve Trapping Rain Water in O(N) time and O(1) space using the two-pointer approach.
Observation: Water trapped at position $i$ = $\min(\text{maxLeft}[i], \text{maxRight}[i]) - \text{height}[i]$.
O(N) / O(1) Two-Pointer Approach:
Maintain left, right pointers and maxLeft, maxRight.
ā¢
Process the pointer with the smaller max: the water at that position is determined by the smaller side.
ā¢
This avoids the $O(N)$ prefix/suffix max arrays (reduces space from $O(N)$ to $O(1)$).
Code Implementation Example
typescript
function trap(height: number[]): number {
let left = 0, right = height.length - 1;
let maxLeft = 0, maxRight = 0;
let water = 0;
while (left < right) {
if (height[left] <= height[right]) {
if (height[left] >= maxLeft) maxLeft = height[left];
else water += maxLeft - height[left];
left++;
} else {
if (height[right] >= maxRight) maxRight = height[right];
else water += maxRight - height[right];
right--;
}
}
return water;
}
console.log(trap([0,1,0,2,1,0,1,3,2,1,2,1])); // 6š”Two-pointer Trapping Rain Water in O(N) time, O(1) space.
šÆ Interview Key Takeaway
Two-pointer rain water reduces O(N) space (prefix arrays) to O(1) by processing the smaller-max side first. Classic interview difficulty: Hard.
#DSA#Two Pointers#Arrays#Trapping Rain Water#Intermediate
Back to all Data Structures & Algorithms Questionsā