Trapping rain water
Given bar heights in an elevation map, each of width 1, compute how much water is trapped after rain. Start with the brute-force solution and its complexity, then improve it to O(n) time (prefix maxima), then to O(1) extra space with two pointers.
TeslaTechnical phone screenNo answer yet. Write the first one; the best answer gets endorsed.