Short Fast JS Solution, O(n) time, 0(1) space


  • 0
    D

    Uses two pointers, one starting from each side and moving towards the middle. Uses ternary operators to compare and set new values. At each iteration it checks whether the left and right highest elevations need to be reset, then adds the difference in elevation from the highest elevation and current pointers then increments them afterwards.

    var trap = function(array) {
        var results = 0,
            l = 0,
            r = array.length - 1,
            lmax = 0,
            rmax = 0;
        
        while(l < r){
            lmax = lmax > array[l] ? lmax : array[l];
            rmax = rmax > array[r] ? rmax : array[r];
            results += lmax < rmax ? lmax - array[l++] : rmax - array[r--]
        }
        return results
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.