You're given an array of non-negative integers where each non-zero integer represents the height of a pillar of width 1. Imagine water being poured over all of the pillars; write a function that returns the surface area of the water trapped between the pillars viewed from the front. Note that spilled water should be ignored.
heights = [0, 8, 0, 0, 5, 0, 0, 10, 0, 0, 1, 1, 0, 3]
48
This problem shares two primary characteristics with other dyanmic programming problems. It's super cool and the solution is super elegant and readable.
Essentially, we have to find the largest pillar to the left and right of each index and obviously the index can't leak out water so it must be less than the smallest of the two pillars. If that condition is satisfied, we will add the the height at that index minus the smallest of the two pillars, else we will simply add nothing as we must be at a pillar.
To find the largest pillar to the right, we will start iterating from the end of the heights array. On the first iteration our height will be zero at that index, which we will mark in an auxillary array, and then we can set up what the largest pillar to the right on the next iteration will be by assserting if the height in the current iteration is larger than the we were provided.
Next, we will iterate over the heights array again, this time from the 0th index, and we are given the largest pillar to the left AND right at that index and with that we can figure out the water area contribution of the particular iteration. We can also assert what the largest pillar on the next iteration will be.
Finally, we will return the water area that we summed up.
Space: O(n)
We keep an array of the left largest pillar for each index.
Time: O(n)
The input array is iterated over once set up the auxillary leftMaxes array and then again to sum up the water area. This ultimately results in O(n).
function waterArea(heights) {
// Write your code here.
const leftMaxes = []
let leftMax = 0
for (let i = 0; i < heights.length; i++) {
const height = heights[i]
leftMaxes[i] = leftMax
leftMax = Math.max(leftMax, height)
}
let rightMax = 0
let waterArea = 0
for(let i = heights.length - 1; i >= 0; i--) {
const height = heights[i]
const minHeight = Math.min(leftMaxes[i], rightMax)
if (height < minHeight) {
waterArea += minHeight - height
} else {
waterArea += 0
}
rightMax = Math.max(rightMax, height)
}
return waterArea
}