Water Level I

Given a non-negative integer array representing the heights of a list of adjacent bars. Suppose each bar has a width of 1. Find the largest amount of water that can be trapped in the histogram.

Assumptions

• The given array is not null

Examples

• { 2, 1, 3, 2, 4 }, the amount of water can be trapped is 1 + 1 = 2 (at index 1, 1 unit of water can be trapped and index 3, 1 unit of water can be trapped)

Solution: Left Right pinch

Use two values, two pointers.

Two values

Two to track the current position, Two to track the current frame. Frame is made up of highest walls currently available.

public int waterLevel(int[] array){
    //sanity check
    if (array.length < 3) return 0;
    
    int left = 0;
    int right = array.length - 1;
    int lmax = array[left];
    int rmax = array[right];
    
    int result = 0;
    
    while (left < right){
        if ( array[left] <= array[right] ){
            //if cur - lmax not negative, water can be held
            result += Math.max(0, lmax - array[left]);
            
            //update lmax in case increase 
            lmax = Math.max(lmax, array[left];
            
            left++;
        } else {
            result += Math.max(0, rmax - array[right]);
            rmax = Math.max(rmax, array[right]);
            right--;
        }
    }
    return result;
}

Time Complexity: O(N) one pass

Space Complexity: O(N) result storage