Problem - Trapping Rain Water

Given $n$ non-negative integers representing an elevation map where the width of each bar is $1$, compute how much water it can trap after raining.

Example: heights $= [0,1,0,2,1,0,1,3,2,1,2,1]$ Answer: $6$ This you can solve with stacks, but also with two pointers or dynamic programming. The stack approach uses the histogram insight: calculate trapped water layer by layer.