Two Pointers Pointers from both ends
157. Trapping Rain Water
You are given an array of non-negative integers heights. Each value is the height of a bar 1 unit wide, and
the bars stand side by side in order, with no gaps between them. Rain falls on the bars until no more water
can stay. Return the total amount of water that stays on top of them.
Water cannot pass through a bar, and any water that reaches either end of the array runs off the edge. A height of 0 means there is no bar at that position, only ground. Each unit of water is a 1 × 1 square.
Example 1
Input: heights = [3, 0, 2, 0, 4, 1, 2]
8Explanation: Positions 1, 2 and 3 lie between the 3 and the 4, so their water rises to 3, the lower of the two. They hold 3, 1 and 3 units. Position 5 lies between the 4 and the last 2 and holds 1 unit, so the total is 8.
Example 2
Input: heights = [2, 5, 7, 7, 4, 1]
0Explanation: The heights climb to the two 7s and then step down, so there is no dip for water to collect in. All the rain runs off.
Example 3
Input: heights = [0, 5, 0, 0, 3, 0]
6Explanation: The two zeros between the 5 and the 3 fill up to 3, the lower wall, and hold 3 units each. The zeros at the two ends hold nothing, because water there runs off the edge.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ heights.length ≤ 1050 ≤ heights[i] ≤ 109
Clarifying questions
What you would ask an interviewer before writing any code.