LESSON 370 OF 441 · DYNAMIC PROGRAMMING

Trapping Rain Water in C#: Dynamic Programming with Prefix Maxima

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 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9

Constraints:

n == height.length
1 <= n <= 3 * 10⁴
0 <= height[i] <= 10⁴

STEP 1 OF 12

Guided

Ctrl + Enter to check

C# · DYNAMIC PROGRAMMING

Trapping Rain Water in C#, explained

Problem overview

The method Trap receives an int[] named height. Each element is the height of a bar of width 1, and the bars stand side by side like an elevation map. After rain, water collects in the gaps between taller bars. The method returns how many units of water the map holds in total.

For [4, 2, 0, 3, 2, 5] the answer is 9. The first bar (4) and the last bar (5) are walls. Between them, the bar of height 2 is covered by 2 units of water, the bar of height 0 by 4, the bar of height 3 by 1 and the next bar of height 2 by 2. The total is 2 + 4 + 1 + 2 = 9. For [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] the answer is 6.

Approach: measure the water above each bar separately

The key observation is that the total is the sum of water columns, one above each bar, and each column can be computed on its own.

The water above bar i can rise only as high as the lower of two walls: the tallest bar somewhere on its left (including itself) and the tallest on its right (including itself). If it rose higher than the lower wall, it would spill over that side. So:

water above bar i = Math.Min(leftMax[i], rightMax[i]) - height[i]

Here leftMax[i] is the tallest bar from the first bar up to i, and rightMax[i] is the tallest from i to the last bar. Both include bar i itself, so the difference is never negative: for a bar that is itself the tallest on a side, one of the two maxima equals its height and the column is 0.

The slow way to get the maxima is to scan left and right from every bar, which costs O(n) per bar and O(n²) in total. The lesson uses dynamic programming instead: each maximum is built from the previous one.

leftMax[0] = height[0], and leftMax[i] = Math.Max(leftMax[i - 1], height[i]).
rightMax[n - 1] = height[n - 1], and rightMax[i] = Math.Max(rightMax[i + 1], height[i]).

For [4, 2, 0, 3, 2, 5], leftMax is [4, 4, 4, 4, 4, 5] and rightMax is [5, 5, 5, 5, 5, 5]. The minimums are [4, 4, 4, 4, 4, 5], and subtracting the heights gives columns of [0, 2, 4, 1, 2, 0], which add up to 9.

Step by step

Store the number of bars in n with height.Length. Every loop below uses it.
Return 0 when n == 0. The next lines read height[0], which needs at least one bar. The constraints promise one, but the check makes the method safe.
Create leftMax as an int[] of size n and set leftMax[0] to height[0]. Nothing comes before the first bar.
Loop from 1 up to n - 1 to fill the rest, since index 0 is done.
Take the larger of the previous leftMax entry and the current height, with Math.Max.
Create rightMax the same way and set its last element to the last height.
Loop from n - 2 down to 0, because the last index is done and this array depends on the entry to its right.
Take the larger of rightMax[i + 1] and height[i].
Start result at 0. It holds the total.
Loop over every bar.
Add the column above bar i: Math.Min(leftMax[i], rightMax[i]) - height[i].
Return result.

The solution in C#

class Solution {
    public int Trap(int[] height) {
        int n = height.Length;
        if (n == 0) return 0;
        int[] leftMax = new int[n];
        leftMax[0] = height[0];
        for (int i = 1; i < n; ++i) {
            leftMax[i] = Math.Max(leftMax[i - 1], height[i]);
        }
        int[] rightMax = new int[n];
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            rightMax[i] = Math.Max(rightMax[i + 1], height[i]);
        }
        int result = 0;
        for (int i = 0; i < n; ++i) {
            result += Math.Min(leftMax[i], rightMax[i]) - height[i];
        }
        return result;
    }
}

The C# details worth knowing:

Arrays have Length, not Count. height.Length is a property, not a method call. Count belongs to List<T>.
New arrays are zero-filled. new int[n] gives n zeros. The solution then overwrites every element, so the starting zeros never matter.
Math.Max and Math.Min are in the System namespace, so a standalone file needs using System;.
++i and i++ do the same thing in a for update, because the value of the expression isn't used there.
No overflow. The largest answer the constraints allow is about 300 million (299,980,000 for two bars of height 10,000 at the ends of 30,000 bars), well inside the range of an int, which holds values up to 2,147,483,647.

Complexity

Let n be the number of bars.

Time: O(n). There are three loops, each over at most n elements, and every step inside them is constant time.

Space: O(n). The two arrays leftMax and rightMax each hold n integers. A two-pointer version of the same idea needs only O(1) extra space, but this lesson keeps the arrays because they make the reasoning easy to see.

Edge cases and common mistakes

One bar. [5] traps nothing: leftMax and rightMax both equal the height, and the column is 0.
Ascending or descending bars. [1, 2, 3] and [3, 2, 1] both return 0, because one side of every bar has no taller wall.
A single pit. [3, 0, 3] returns 3, and [2, 0, 2] returns 2.
Uneven walls. [5, 4, 1, 2] returns 1. The water above the bar of height 1 rises only to 2, the height of the lower wall on the right, and not to 4.
Using only one maximum. Subtracting the height from leftMax alone ignores the right wall and counts water that would spill out.
Leaving the bar out of its own maximum. If the maxima didn't include the bar itself, the formula could go negative on peaks.
Wrong loop direction. rightMax must be filled from right to left, since each entry needs the one after it.
Off-by-one starts. Starting the first loop at 0 would read leftMax[-1], which throws an IndexOutOfRangeException. Starting the second loop at n - 1 would read rightMax[n], which throws as well.

Testing

[0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] gives 6.
[4, 2, 0, 3, 2, 5] gives 9.
[5] gives 0.
[1, 2, 3] gives 0.
[3, 0, 3] gives 3.
[5, 4, 1, 2] gives 1.

Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free