Crack the Backend

Problem Statement

You are given an array height of non-negative integers representing an elevation map: each height[i] is the height of a bar of width 1. After rain, water can be trapped between bars. Return the total amount of water that can be trapped (sum over all columns of water height in that column).

Key Observations

Two pointers: Maintain left and right pointers and maxL, maxR (max height seen from left/right). The water level at the current position (the side we process) is bounded by min(maxL, maxR); we process the side with the smaller max so we know the water at that column is min(maxL, maxR) - height[current]. Advance that pointer and update the corresponding max.
Monotonic stack alternative: when a bar higher than stack top appears, we form a "pit" and can add the water layer between the previous bar (stack top) and the current bar.

Approach

High-level: left=0, right=n-1, maxL=0, maxR=0, total=0. While left < right: if height[left] <= height[right], water at left = maxL - height[left] (if positive), maxL = max(maxL, height[left]), left++; else same from right. Sum water.

Steps: int l=0, r=n-1, maxL=0, maxR=0, sum=0; while (l<r) { if (height[l]<=height[r]) { if (height[l]>=maxL) maxL=height[l]; else sum+=maxL-height[l]; l++; } else { ... } } return sum.

Implementation

Java

public int trap(int[] height) {
    int left = 0, right = height.length - 1, maxL = 0, maxR = 0, total = 0;

    while (left < right) {
        if (height[left] <= height[right]) {
            if (height[left] >= maxL) {
                maxL = height[left];
            }
            else {
                total += maxL - height[left];
            }

            left++;
        }
        else {
            if (height[right] >= maxR) {
                maxR = height[right];
            }
            else {
                total += maxR - height[right];
            }

            right--;
        }
    }

    return total;
}

Test Cases

Example 1

Input

height = [0,1,0,2,1,0,1,3,2,1,2,1]

Expected

6

Explanation

6 units trapped.

Complexity Analysis

Time: O(n).
Space: O(n) for stack.

Follow-ups

Previous smaller; range queries.