Stretch Problem: Trapping Rain Water (hard)

This problem is optional and it is hard. Nothing later in the course depends on it. Try it when you want the hardest array question in this course, and read the solution when you are ready: the two pointer idea it teaches shows up again and again.

Problem Statement

You are given an array height where height[i] is the height of a bar of width 1 standing at position i. The bars sit side by side, so the gaps between taller bars trap rainwater.

Return how many units of water are trapped after it rains.

Examples

Example 1

• Input: height =