The Question
Coding

Trapping Rain Water

Given an elevation map represented as an integer array where each element is the height of a bar of width 1, compute the total amount of water that can be trapped between the bars after rainfall.
Java
Two Pointers
Questions & Insights

Thinking Process

The water trapped at any given index is determined by the minimum of the maximum height to its left and the maximum height to its right, minus the current height: Water[i] = \min(\text{maxLeft}_i, \text{maxRight}_i) - \text{height}[i].
Rather than pre-calculating two arrays for left/right maximums (which costs O(N) space), we can use a Two-Pointer approach to calculate the volume in a single pass.
By maintaining leftMax and rightMax variables and moving pointers from both ends inward, we can always process the side with the smaller current height. This works because the water level at that pointer is bottlenecked by its own side's maximum, given we already know the other side has a boundary at least as high.
Implementation Breakdown

Problem Set

Functional Requirement: Given non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
Constraints:
n == \text{height.length}
1 \le n \le 2 \cdot 10^4
0 \le \text{height}[i] \le 10^5
Time complexity should be O(N).
Space complexity should ideally be O(1).

Approach

Algorithm: Two-Pointer Approach.
Data Structure: None (Primitive variables).
Complexity:
Time: O(N) where N is the number of elements in the elevation map.
Space: O(1) as we only store a few integer variables.

Implementation