LESSON 371 OF 442 · DYNAMIC PROGRAMMING

Trapping Rain Water in Kotlin: Prefix and Suffix Maximum Arrays

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

KOTLIN · DYNAMIC PROGRAMMING

Trapping Rain Water in Kotlin, explained

Problem overview

The function trap receives height, an IntArray that describes an elevation map. Each element is the height of a bar of width 1. After it rains, water collects in the dips between taller bars. The function returns how many units of water stay trapped.

For [4, 2, 0, 3, 2, 5] the answer is 9. Above the bar of height 2 at index 1 the water rises to level 4, because the tallest bar on its left is 4 and the tallest on its right is 5, and the lower of the two sets the level. That column holds 2 units. The columns at indices 2, 3 and 4 hold 4, 1 and 2 units, which makes 9 together. The two end bars hold nothing.

The array can hold up to 30,000 bars, each up to 10,000 high.

Approach: water above a bar depends on two walls

Look at a single bar. Water above it is held in by the tallest bar somewhere on its left and the tallest somewhere on its right. The water level can only rise to the lower of those two walls, and the bar itself already fills the bottom of the column. So the water above bar i is:

min(tallest bar at or left of i, tallest bar at or right of i) - height[i]

Both maxima include bar i, so the result is never negative. For a bar that is itself the tallest on one side, the formula gives 0.

The brute-force way finds those two maxima by scanning left and right from every bar, which is O(n²) in total. But the maximum up to bar i is either the maximum up to bar i - 1 or bar i itself, so each entry can reuse the one before it. That reuse is the dynamic programming in this lesson. Precomputing one array for each direction makes every bar's answer a constant-time lookup.

For [4, 2, 0, 3, 2, 5] the two arrays are:

leftMax  = [4, 4, 4, 4, 4, 5]
rightMax = [5, 5, 5, 5, 5, 5]

The smaller value at each index is 4, 4, 4, 4, 4, 5. Subtracting the heights 4, 2, 0, 3, 2, 5 gives 0, 2, 4, 1, 2, 0, and these add up to 9.

Step by step

Store the number of bars in a val named n. Every loop uses it.
Return 0 if n == 0. No bars hold no water, and the next lines read height[0], which needs at least one bar.
Create leftMax as an IntArray of n zeros, and set leftMax[0] to height[0]. Nothing comes before the first bar, so the tallest bar up to it is the bar itself.
Loop i over 1 until n. Index 0 is already set.
Set leftMax[i] to maxOf(leftMax[i - 1], height[i]): the tallest bar up to i is the tallest before it or bar i itself.
Create rightMax the same way, with rightMax[n - 1] set to height[n - 1].
Loop i over n - 2 downTo 0. This range counts down and includes both ends. The last index is already set, so the loop starts one before it.
Set rightMax[i] to maxOf(rightMax[i + 1], height[i]). It is the mirror image of the first loop.
Create result with var, starting at 0.
Loop i over 0 until n to visit each bar once.
Add the water above bar i: minOf(leftMax[i], rightMax[i]) - height[i].
Return result.

The solution in Kotlin

class Solution {
    fun trap(height: IntArray): Int {
        val n = height.size
        if (n == 0) return 0
        val leftMax = IntArray(n)
        leftMax[0] = height[0]
        for (i in 1 until n) {
            leftMax[i] = maxOf(leftMax[i - 1], height[i])
        }
        val rightMax = IntArray(n)
        rightMax[n - 1] = height[n - 1]
        for (i in n - 2 downTo 0) {
            rightMax[i] = maxOf(rightMax[i + 1], height[i])
        }
        var result = 0
        for (i in 0 until n) {
            result += minOf(leftMax[i], rightMax[i]) - height[i]
        }
        return result
    }
}

The Kotlin details worth a closer look:

IntArray is filled with zeros. IntArray(n) creates an array of n primitive int values, all 0. It is fixed in size, and unlike List<Int> it doesn't box each number.
height.size. Arrays have a size property, not a length or a size() method.
Ranges. 1 until n excludes n, so it covers the indices 1 to n - 1. When n is 1, it is empty. n - 2 downTo 0 counts down and includes both ends. When n is 1, it starts at -1 and is also empty. A range written 0..n would include n and read past the end of the array.
maxOf and minOf. These are top-level functions of the standard library that take two values. They need no import.
The sum fits in an Int. The most water the constraints allow is under 30,000 times 10,000, or 300 million. That is below the Int limit of about 2.1 billion, so Int arithmetic can't overflow here.
if (n == 0) return 0. A single-line if without braces is fine for one statement.

Complexity

Time: O(n). There are three passes over the array, one for each loop, and each does constant work per bar.

Space: O(n). The two helper arrays have n elements each. A two-pointer method that moves inward from both ends gets the same answer in O(1) extra space, but this lesson builds the arrays because each step is easy to see and check.

Edge cases and common mistakes

A single bar. [5] has no walls around it, and the function returns 0. Both maxima equal the bar, so the difference is 0.
Sorted bars. [1, 2, 3] and [5, 4, 3, 2, 1] both return 0. Water needs a taller bar on each side.
A flat map. Equal heights, like [10000, 10000, ...], hold nothing.
A deep pit. [3, 0, 3] returns 3. With 30,000 bars where only the two ends are 10,000 high and the rest are 0, the answer is 299,980,000, which still fits in an Int.
Using only one maximum. With leftMax alone, water would be counted over bars that have no right wall. Both walls matter, and the lower one decides.
Forgetting to subtract the bar. The column's capacity counts from the ground, but the bar already fills part of it. Subtract height[i].
Starting the loops at the wrong index. The first entry of each array is set separately. Looping from 0 in leftMax would read leftMax[-1] and throw an ArrayIndexOutOfBoundsException.

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, 3, 2, 1] gives 0.

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

Start learning free