
function volumeOfHistogram(input) {
    if (!input.length) {
        return 0;
    }

    // find last max - O(n)
    let maxIdx = 0;
    let lastMax = [0];
    for (let idx = 1; idx < input.length; idx++) {
        if (input[idx] >= lastMax[idx - 1]) {
            lastMax[idx] = input[idx];
            maxIdx = idx;
        }
        else {
            lastMax[idx] = lastMax[idx - 1];
        }
    }

    // find next max - O(n)
    let nextMax = new Array(input.length);
    nextMax[input.length - 1] = 0;
    for (let idx = input.length - 2; idx >= 0; idx--) {
        if (input[idx] >= nextMax[idx + 1]) {
            nextMax[idx] = input[idx];
        }
        else {
            nextMax[idx] = nextMax[idx + 1];
        }
    }

    // process volume on left half O(n)
    let leftVolume = 0;
    for (let idx = 0; idx < maxIdx; idx++) {
        leftVolume += (lastMax[idx] - input[idx]);
    }

    // process volume on right half O(n)
    let rightVolume = 0;
    for (let idx = maxIdx + 1; idx < input.length; idx++) {
        rightVolume += (nextMax[idx] - input[idx]);
    }

    // return sum of volumes
    return leftVolume + rightVolume;
}


let testCases = [
    [0, 0, 4, 0, 0, 6, 0, 0, 3, 0, 5, 0, 1, 0, 0, 0]
];

for (let testInput of testCases) {
    console.log(testInput);
    console.log(volumeOfHistogram(testInput));
}

module.exports = volumeOfHistogram;