The Question
Coding

Trapping Rain Water

Given a non-negative integer array representing the heights of vertical bars on a 2D map where each bar has a width of 1, compute the total volume of water that can be contained within the structures after a rainfall.
Java
Two Pointers
Questions & Insights

Clarifying Questions

What is the range of the input array size and the maximum height value? (Assumption: N up to 10^5, heights up to 10^5, fitting in standard integer types).
How should empty or null inputs be handled? (Assumption: Return 0).
Is the input guaranteed to contain only non-negative integers? (Assumption: Yes, elevations cannot be negative).
Is an $O(n)$ time complexity and $O(1)$ space complexity preferred over $O(n)$ space solutions? (Assumption: Yes, the two-pointer approach is optimal).

Thinking Process

Recognize that the amount of water trapped at any index i depends on the "bottleneck" height: the minimum of the maximum heights to its left and right, minus its own height.
To optimize space, use a two-pointer approach starting from both ends of the array. Maintain leftMax and rightMax variables to track the highest boundaries encountered so far from each direction.
At each step, compare leftMax and rightMax. If leftMax is smaller, we know the water trapped at the left pointer is limited by leftMax, regardless of what lies further to the right. Process the left pointer and move inward.
If rightMax is smaller or equal, the water trapped at the right pointer is limited by rightMax. Process the right pointer and move inward. Accumulate the differences into a total volume variable.
Implementation Breakdown

Problem Set

Functional Requirement: Calculate the total units of water trapped between elevation bars.
Constraints:
Time Complexity: O(n).
Space Complexity: O(1) (excluding input).
Handle edge cases like arrays with fewer than 3 elements where no water can be trapped.

Approach

Algorithm: Two Pointers.
Data Structure: None (Primitive variables).
Complexity:
Time: O(n) where n is the length of the elevation map.
Space: O(1) as we only store a few pointers and variables.

Implementation