AlgoDaily

Trapping Rain Water

Read at your own pace. Code execution, quizzes, progress tracking, and the AI tutor are available in the interactive view with JavaScript enabled.

Description

The Trapping Rain Water Challenge: A Deep Dive

Imagine you're looking at an elevation map displaying rainfall over a region's landscape. The map consists of bars of varying heights, each representing different elevations. Can you determine the amount of rainwater that this uneven terrain can hold?

Elevation Map

Problem Setup

We'll simplify the problem by using a one-dimensional array of non-negative integers. Each integer represents the height of the land at different points. The objective is to calculate the volume of rainwater that can be trapped by this series of elevations.

To better visualize this, consider the diagram below, which illustrates various elevation maps and the potential rainwater they can hold. Think of it like a game of Tetris; we aim to find how many units of rainwater could be accommodated in the available gaps.

Rainwater in Elevation Maps

Constraints and Performance Metrics

  • Length of the array <= 100000
  • Values in the array >=0
  • The final answer would fit in the Integer range(< 2^32)
  • Expected time complexity : O(n)
  • Expected space complexity : O(1)

Solving the Problem

As usual, we'll solve this by examining some test cases to get a feel for the varying scenarios. After we've developed an intuition, we can try to identify a pattern towards a solution.

The previous image shows that we can only trap water if there is a valley-like pattern in the elevation map, meaning a low area between higher areas. So we want to find a segment where the shape is as follows: the height of the bars have a decrease, followed by an increase in height, to "catch" the rain.

Let's also look at a few maps which don't trap any water.

Don't trap

Solving the Problem

We can come up with several methods of computing the amount of rainwater trapped by an elevation map. We should always start by brute forcing it, and ask ourselves how we'd manually determine the result we want.

Let's take a super simple example, [5, 3, 5]. Picture it below:

X R X
X R X
X X X
X X X
X X X
5 3 5

0 1 2   <-- index

Well, starting at the first element 5, we know that no rain can be trapped. So we move on. At the second element, 3, things get interesting: we know based on our observation of the element before it, it can carry up to 2 extra units of rain. Because the element that follows is also a 5, it makes sense that that shape can hold 2.

But suppose one of the surrounding hills was 6 instead:

    X
X R X
X R X
X X X
X X X
X X X
5 3 6

0 1 2   <-- index

Any rain that would reach 5 units worth can be pictured as "sliding off" the elements at index 0 and 1. So at every element, we actually want to find the two highest peaks surrounding said element, and take the second highest.

So that's the brute force solution. Here, let's see this visually: we'll discuss one simple but efficient way to calculate the result.

All we need is to determine what the maximum water level can be at each column of the whole map. To get this, read and understand the below statement very carefully, and think about it:

The maximum level of water at index i is the minimum value of the maximum heights in both directions from i. water_level(i) = min(max_height[0:i-1], max_height[i+1:n])

Definitions

After determining the maximum level of water, we can just subtract the height at i from the maximum level of water to get the water height at i.

Now we need to solve how to get the maximum water levels. Believe it or not, it's already been solved by the quote I gave you earlier. Do you see it?

Here it is: we need to get the maximum height from both sides of i (left and right) to get the maximum water level at i. What if we can divide the problem into two similar problems with different directions? We can do this with two new arrays. See the image below:

left-right

First, we go from left to right and keep the maximum height found until now in a new array. Think of it as a running max height from the left.

```java
public class Main {
    public static int totalRain(int[] heights) {
        if (heights == null || heights.length <= 2)
            return 0;
        
        int N = heights.length;
        int max = 0;
        int left[] = new int[N];
        int right[] = new int[N];

        // scan from left to right
        max = heights[0];
        left[0] = max;
        for (int i = 1; i < N; i++) {
            if (heights[i] > max) {
                max = heights[i];
            }
            left[i] = max;
        }

        return left;
    }

    public static void main(String args[]) {
        // uncomment a different array to see the working on a different array
        // int myArr[] = {0, 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1, 0, 0}; // should be 6
        // int myArr[] = {0, 0, 1, 0, 2, 4, 4, 4, 2, 3, 1, 0, 2, 4, 3, 1, 0, 1}; // should be 14
        // int myArr[] = {0, 0, 1, 2, 4, 4, 4, 3, 1, 0, 0, 0}; // should be 0
        int myArr[] = { 5, 1, 2, 4, 4, 4, 3, 1, 0, 0, 0 }; // should be 5

        System.out.println(totalRain(myArr));
    }
}
```
```py
def totalRain(heights):
    if heights == None or len(heights) <= 2:
        return 0
    
    N = len(heights)
    max = 0
    left = [0] * N
    right = [0] * N

    # scan from left to right
    max = heights[0]
    left[0] = max
    for i in range(N):
        if heights[i] > max:
            max = heights[i]
        left[i] = max
    
    return left

# uncomment a different array to see the working on a different array
# arr = [0, 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1, 0, 0] # should be 6
# arr = [0, 0, 1, 0, 2, 4, 4, 4, 2, 3, 1, 0, 2, 4, 3, 1, 0, 1] # should be 14
# arr = [0, 0, 1, 2, 4, 4, 4, 3, 1, 0, 0, 0] # should be 0
arr = [ 5, 1, 2, 4, 4, 4, 3, 1, 0, 0, 0 ] # should be 5

print(totalRain(arr));
```
```javascript
function totalRain(heights) {
    if (heights === null || heights.length <= 2)
        return 0;
    
    let N = heights.length;
    let max = 0;
    let left = Array(N).fill(0);
    let right = Array(N).fill(0);

    // scan from left to right
    max = heights[0];
    left[0] = max;
    for (let i = 0; i < N; i++) {
        if (heights[i] > max) {
            max = heights[i];
        }
        left[i] = max;
    }

    return left;
}

// uncomment a different array to see the working on a different array
// let arr = [0, 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1, 0, 0]; // should be 6
// let arr = [0, 0, 1, 0, 2, 4, 4, 4, 2, 3, 1, 0, 2, 4, 3, 1, 0, 1]; // should be 14
// let arr = [0, 0, 1, 2, 4, 4, 4, 3, 1, 0, 0, 0]; // should be 0
let arr = [ 5, 1, 2, 4, 4, 4, 3, 1, 0, 0, 0 ]; // should be 5

console.log(totalRain(arr));
```
```cpp
#include<iostream>

using namespace std;

int totalRain(int heights[], int N) {
    if(heights == NULL || N <= 2)
        return 0;

    int max = 0;
    int left[N];
    int right[N];

    // scan from left to right
    max = heights[0];
    left[0] = max;
    for(int i = 1; i < N; i++) {
        if(heights[i] > max) {
            max = heights[i];
        }
        left[i] = max;
    }

    return *left;
}

int main() {
    // uncomment a different array to see the working on a different array
    // int arr[] = {0, 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1, 0, 0}; // should be 6
    // int arr[] = {0, 0, 1, 0, 2, 4, 4, 4, 2, 3, 1, 0, 2, 4, 3, 1, 0, 1}; // should be 14
    // int arr[] = {0, 0, 1, 2, 4, 4, 4, 3, 1, 0, 0, 0}; // should be 0
    int arr[] = { 5, 1, 2, 4, 4, 4, 3, 1, 0, 0, 0 }; // should be 5
    const int size = sizeof(arr)/sizeof(arr[0]);

    cout<<totalRain(arr,size)<<endl;

    return 0;
}
```
```csharp
using System;

public class Program
{
    static int totalRain(int[] heights)
    {
        if (heights == null || heights.Length <= 2)
            return 0;

        int N = heights.Length;
        int max = 0;
        int[] left = new int[N];
        int[] right = new int[N];

        // scan from left to right
        max = heights[0];
        left[0] = max;
        for(int i=1; i < N; i++) 
        {
            if(heights[i] > max) 
            {
                max = heights[i];
            }
            left[i] = max;
        }

        return left[0];
    }

    public static void Main()
    {
        // uncomment a different array to see the working on a different array
        // int[] arr = {0, 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1, 0, 0}; // should be 6
        // int[] arr = {0, 0, 1, 0, 2, 4, 4, 4, 2, 3, 1, 0, 2, 4, 3, 1, 0, 1}; // should be 14
        // int[] arr = {0, 0, 1, 2, 4, 4, 4, 3, 1, 0, 0, 0}; // should be 0
        int[] arr = { 5, 1, 2, 4, 4, 4, 3, 1, 0, 0, 0 }; // should be 5

        Console.WriteLine(totalRain(arr));
    }
}
```
```go
package main

import (
	"fmt"
)

func totalRain(heights []int) int {
	if heights == nil || len(heights) <= 2 {
		return 0
	}

	N := len(heights)
	max := 0
	left := make([]int, N)
	right := make([]int, N)

	// scan from left to right
	max = heights[0]
	left[0] = max
	for i := 1; i < N; i++ {
		if heights[i] > max {
			max = heights[i]
		}
		left[i] = max
	}

	return left[0]
}

func main() {
	// uncomment a different array to see the working on a different array
	// arr := []int{0, 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1, 0, 0} // should be 6
	// arr := []int{0, 0, 1, 0, 2, 4, 4, 4, 2, 3, 1, 0, 2, 4, 3, 1, 0, 1} // should be 14
	// arr := []int{0, 0, 1, 2, 4, 4, 4, 3, 1, 0, 0, 0} // should be 0
	arr := []int{5, 1, 2, 4, 4, 4, 3, 1, 0, 0, 0} // should be 5

	fmt.Println(totalRain(arr))
}
```

Right to Left

Do the same for right to left

We can do the exact same thing from right to left. This will be accumulated in a new array named right[].

So finally, we get the two arrays left[] and right[] that we can use to get the maximum water level at each column. See the code to understand how we got these two.

```java
public class Main {
    public static int totalRain(int[] heights) {
        if (heights == null || heights.length <= 2)
            return 0;
        
        int N = heights.length;
        int max = 0;
        int left[] = new int[N];
        int right[] = new int[N];

        // scan from left to right
        max = heights[0];
        left[0] = max;
        for (int i = 1; i < N; i++) {
            if (heights[i] > max) {
                max = heights[i];
            }
            left[i] = max;
        }
        // scan from right to left
        max = heights[N - 1];
        right[N - 1] = max;
        for (int i = N - 2; i >= 0; i--) {
            if (heights[i] > max) {
                max = heights[i];
            }
                right[i] = max;
        }
    }

    public static void main(String args[]) {
        // uncomment a different array to see the working on a different array
        // int myArr[] = {0, 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1, 0, 0}; // should be 6
        // int myArr[] = {0, 0, 1, 0, 2, 4, 4, 4, 2, 3, 1, 0, 2, 4, 3, 1, 0, 1}; // should be 14
        // int myArr[] = {0, 0, 1, 2, 4, 4, 4, 3, 1, 0, 0, 0}; // should be 0
        int myArr[] = { 5, 1, 2, 4, 4, 4, 3, 1, 0, 0, 0 }; // should be 5

        System.out.println(totalRain(myArr));
    }
}
```
```py
def totalRain(heights):
    if heights == None or len(heights) <= 2:
        return 0
    
    N = len(heights)
    max = 0
    left = [0] * N
    right = [0] * N

    # scan from left to right
    max = heights[0]
    left[0] = max
    for i in range(N):
        if heights[i] > max:
            max = heights[i]
        left[i] = max

    # scan from right to left
    max = heights[N - 1];
    right[N - 1] = max
    for i in range(N-2, 0, -1):
        if heights[i] > max:
            max = heights[i]

        right[i] = max
    
    return right

print(totalRain(arr))
```
```javascript
function totalRain(heights) {
    if (heights === null || heights.length <= 2)
        return 0;

    let N = heights.length;
    let max = 0;
    let left = Array(N).fill(0);
    let right = Array(N).fill(0);

    // scan from left to right
    max = heights[0];
    left[0] = max;
    for (let i = 1; i < N; i++) {
        if (heights[i] > max) {
            max = heights[i];
        }
        left[i] = max;
    }
    // scan from right to left
    max = heights[N - 1];
    right[N - 1] = max;
    for (let i = N - 2; i >= 0; i--) {
        if (heights[i] > max) {
            max = heights[i];
        }
        right[i] = max;
    }
    return right;
}

console.log(totalRain(arr));
```
```cpp
#include<bits/stdc++.h>
using namespace std;

int totalRain(vector<int> heights) {
    if (heights.empty() || heights.size() <= 2)
        return 0;

    int N = heights.size();
    int maxVal = 0;
    vector<int> left(N);
    vector<int> right(N);

    // scan from left to right
    maxVal = heights[0];
    left[0] = maxVal;
    for (int i = 1; i < N; i++) {
        if (heights[i] > maxVal) {
            maxVal = heights[i];
        }
        left[i] = maxVal;
    }
    // scan from right to left
    maxVal = heights[N - 1];
    right[N - 1] = maxVal;
    for (int i = N - 2; i >= 0; i--) {
        if (heights[i] > maxVal) {
            maxVal = heights[i];
        }
        right[i] = maxVal;
    }

    return right;
}

int main() {
    vector<int> heights = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
    cout << totalRain(heights) << endl;
}
```
```csharp
public class Main {
    public static int[] totalRain(int[] heights) {
        if (heights == null || heights.Length <= 2)
            return new int[0];

        int N = heights.Length;
        int max = 0;
        int[] left = new int[N];
        int[] right = new int[N];

        // scan from left to right
        max = heights[0];
        left[0] = max;
        for (int i = 1; i < N; i++) {
            if (heights[i] > max) {
                max = heights[i];
            }
            left[i] = max;
        }
        // scan from right to left
        max = heights[N - 1];
        right[N - 1] = max;
        for (int i = N - 2; i >= 0; i--) {
            if (heights[i] > max) {
                max = heights[i];
            }
            right[i] = max;
        }
        return right;
    }

    static void Main(string[] args) {
        int[] heights = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        Console.WriteLine(totalRain(heights));
    }
}
```
```go
package main

import (
	"fmt"
)

func totalRain(heights []int) []int {
	if heights == nil || len(heights) <= 2 {
		return nil
	}

	N := len(heights)
	maxVal := 0
	left := make([]int, N)
	right := make([]int, N)

	// scan from left to right
	maxVal = heights[0]
	left[0] = maxVal
	for i := 1; i < N; i++ {
		if heights[i] > maxVal {
			maxVal = heights[i]
		}
		left[i] = maxVal
	}

	// scan from right to left
	maxVal = heights[N - 1]
	right[N - 1] = maxVal
	for i := N - 2; i >= 0; i-- {
		if heights[i] > maxVal {
			maxVal = heights[i]
		}
		right[i] = maxVal
	}

	return right
}

func main() {
	arr := []int{0, 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}
	fmt.Println(totalRain(arr))
}
```

Final Solution

Maximum Water Level at columni

As explained previously in the quote, now we can get the maximum water level at index/column i pretty easily. Before that, think about the values we currently have at hand on left[] and right[] arrays.

left[i] = Maximum value of heights if we keep going to left from i.
right[i] = Maximum value of heights if we keep going to right from i.

So what we need to do is get the minimum of these two to get the maximum water level at i. Remember, this is not yet what we want at each column/index. We want to have the amount of water at each column. So we subtract the height at i from the maximum level of water. That would be our desired value at each index.

max_level_of_water[i] = min(left[i], right[i])
water(i) = max_level_of_water[i] - height[i]

maxLevelOfWater[i] = Math.min(left[i], right[i]);
water[i] = maxLevelOfWater[i] - height[i];

maxLevelOfWater[i] = Math.min(left[i], right[i]);
water[i] = maxLevelOfWater[i] - height[i];

max_level_of_water[i] = min(left[i], right[i])
water[i] = max_level_of_water[i] - height[i]

maxLevelOfWater[i] = std::min(left[i], right[i]);
water[i] = maxLevelOfWater[i] - height[i];

maxLevelOfWater[i] = Math.Min(left[i], right[i]);
water[i] = maxLevelOfWater[i] - height[i];

maxLevelOfWater[i] = int(math.Min(float64(left[i]), float64(right[i])))
water[i] = maxLevelOfWater[i] - height[i]

Finally, we can sum up the whole max_level_of_water array to get the final result. But do we really need another array max_level_of_water for this?

No, we don't! We can get the sum directly by calculating from left[] and right[] at each column and adding them (starting from 0) during the iteration. The modified pseudo code is below:

result = sum(min(left[i], right[i]) - height[i]) ; for i = 0..n

int result = 0;
for (int i = 0; i < n; i++) {
    result += Math.min(left[i], right[i]) - height[i];
}

let result = 0;
for (let i = 0; i < n; i++) {
    result += Math.min(left[i], right[i]) - height[i];
}

result = sum(min(left[i], right[i]) - height[i] for i in range(n))

int result = 0;
for (int i = 0; i < n; i++) {
    result += std::min(left[i], right[i]) - height[i];
}

int result = 0;
for (int i = 0; i < n; i++) {
    result += Math.Min(left[i], right[i]) - height[i];
}

result := 0
for i := 0; i < n; i++ {
    result += min(left[i], right[i]) - height[i]
}

To understand this, I am giving you the below diagram showing the values of an example at each step and arrays.

solution

So the final solution is given below:

```java
public class Main {
    public static int totalRain(int[] heights) {
        if (heights == null || heights.length <= 2)
            return 0;
        
        int N = heights.length;
        int max = 0;
        int left[] = new int[N];
        int right[] = new int[N];

        // scan from left to right
        max = heights[0];
        left[0] = max;
        for (int i = 1; i < N; i++) {
            if (heights[i] > max) {
                max = heights[i];
            }
            left[i] = max;
        }
        // scan from right to left
        max = heights[N - 1];
        right[N - 1] = max;
        for (int i = N - 2; i >= 0; i--) {
            if (heights[i] > max) {
                max = heights[i];
            }
                right[i] = max;
        }

        // calculate total
        int result = 0;
        for (int i = 0; i < N; i++) {
            result += Math.min(left[i], right[i]) - heights[i];
        }
        return result;
    }

    public static void main(String args[]) {
        // uncomment a different array to see the working on a different array
        // int myArr[] = {0, 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1, 0, 0}; // should be 6
        // int myArr[] = {0, 0, 1, 0, 2, 4, 4, 4, 2, 3, 1, 0, 2, 4, 3, 1, 0, 1}; // should be 14
        // int myArr[] = {0, 0, 1, 2, 4, 4, 4, 3, 1, 0, 0, 0}; // should be 0
        int myArr[] = { 5, 1, 2, 4, 4, 4, 3, 1, 0, 0, 0 }; // should be 5

        System.out.println(totalRain(myArr));
    }
}
```
```javascript
function totalRain(heights){
  if (heights === null || heights.length <= 2) return 0;

  let N = heights.length;
  let max = 0;
  let left = new Array(N);
  let right = new Array(N);

  max = heights[0];
  left[0] = max;
  for (let i = 1; i < N; i++) {
    if (heights[i] > max) {
        max = heights[i];
    }
    left[i] = max;
  }

  max = heights[N-1];
  right[N-1] = max;
  for (let i = N - 2; i >= 0; i--) {
    if (heights[i] > max) {
      max = heights[i];
    }
    right[i] = max;
  }

  let result = 0;
  for (let i = 0; i < N; i++) {
    result += Math.min(left[i], right[i]) - heights[i];
  }
  return result;
}

var myArr = [5, 1, 2, 4, 4, 4, 3, 1, 0, 0, 0];
console.log(totalRain(myArr));
```
```python
def totalRain(heights):
  if not heights or len(heights) <= 2:
    return 0
    
  N = len(heights)
  max_h = 0
  left = [0] * N
  right = [0] * N
  max_h = heights[0]
  left[0] = max_h

  for i in range(1, N):
    if heights[i] > max_h:
      max_h = heights[i]
    left[i] = max_h

  max_h = heights[N - 1]
  right[N - 1] = max_h
  for i in range(N - 2, -1, -1):
    if heights[i] > max_h:
      max_h = heights[i]
    right[i] = max_h

  result = 0
  for i in range(N):
    result += min(left[i], right[i]) - heights[i]
  return result

myArr = [5, 1, 2, 4, 4, 4, 3, 1, 0, 0, 0]
print(totalRain(myArr))
```
```cpp
#include <iostream>
#include <vector>
#include <algorithm>

int totalRain(std::vector<int> heights) {
    if (heights.empty() || heights.size() <= 2)
        return 0;

    std::vector<int> left(heights.size()), right(heights.size());
    int max_v = heights[0], result = 0;
    left[0] = max_v;

    for (int i = 1; i < heights.size(); i++) {
        max_v = std::max(max_v, heights[i]);
        left[i] = max_v;
    }

    max_v = heights.back();
    right.back() = max_v;

    for (int i = heights.size() - 2; i >= 0; i--) {
        max_v = std::max(max_v, heights[i]);
        right[i] = max_v;
    }

    for (int i = 0; i < heights.size(); i++)
        result += std::min(left[i], right[i]) - heights[i];

    return result;
}

int main() {
    std::vector<int> myArr = {5, 1, 2, 4, 4, 4, 3, 1, 0, 0, 0};
    std::cout << totalRain(myArr) << std::endl;
    return 0;
}
```
```csharp
public static void Main(string[] args) {  
    int[] myArr = { 5, 1, 2, 4, 4, 4, 3, 1, 0, 0, 0 };
    Console.WriteLine(TotalRain(myArr));  
}  

public static int TotalRain(int[] heights) {      
    int n = heights.Length;  
    if (heights == null || n <= 2)  
        return 0;  

    int left_max = 0, right_max = 0;
    int[] left = new int[n];  
    int[] right = new int[n];  

    left[0] = heights[0];  
    for(int i = 1; i < n; i++) {  
      left[i] = Math.Max(left[i - 1], heights[i]);  
    } 

    right[n - 1] = heights[n - 1];  
    for (int i = n - 2; i >= 0; i--) {  
      right[i] = Math.Max(right[i + 1], heights[i]);
    }

    for(int i=0; i<n; i++) {
      total_amt += Math.Min(left[i], right[i]) - heights[i];  
    }
    return total_amt;
}
```
```go 
package main
 
import (
	"fmt"
)
 
func TotalRain(heights []int) int {
	if heights == nil || len(heights) <= 2 {
		return 0
	}
	left := make([]int, len(heights))
	right := make([]int, len(heights))
	max := heights[0]
	left[0] = heights[0]
	for i := 1; i < len(heights); i++ {
		if heights[i] > max {
			max = heights[i]
		}
		left[i] = max
	}
	max = heights[len(heights)-1]
	right[len(heights)-1] = max
	for i := len(heights) - 2; i >= 0; i-- {
		if heights[i] > max {
			max = heights[i]
		}
		right[i] = max
	}
	result := 0
	for i := 0; i < len(heights); i++ {
		result += min(left[i], right[i]) - heights[i]
	}
	return result
}
	
func min(a, b int) int {
	if a < b {
		return a
	} else {
		return b
	}
}
 
func main() {
	heights := []int{5, 1, 2, 4, 4, 4, 3, 1, 0, 0, 0}
	fmt.Println(TotalRain(heights))
}
```

Complexity Analysis

Complexity Analysis

We are iterating through the heights input array 3 times sequentially.

  1. While creating left[].
  2. While creating right[].
  3. While summing result.

So the time complexity of the algorithm is O(3n) = O(n) where n is the length of the input array height.

We are creating two new arrays of the same length as height. So the space complexity is also O(2n) = O(n).

Python Solution

Code for Trapping Rain Water

This code is intentionally made very precise and concise by following Functional Programming principles. We do the following step by step to get the result:

  1. First we check the corner/simplest cases and return 0 if found.
  2. So our final result will be a sum of something.
  3. sum of what? sum of minimum of two values calculated from heights. We also need to subtract heights[i] from them.
  4. min of which two values? Values calculated from left-to-right at each index and right-to-left at each index.
  5. So we can return all these with that one statement.
```python
def totalRain(heights):
    if not heights or len(heights) <= 2:
        return 0
    
    return sum(
        [min(
            max(heights[:i+1] or heights[:1]),
            max(heights[i:] or heights[-1:])
            ) - heights[i] for i in range(len(heights))
        ]
    )


if __name__ == '__main__':
        # uncomment a different array to see the working on a different array
        # myArr = [0, 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1, 0, 0] # should be 6
        # myArr = [0, 0, 1, 0, 2, 4, 4, 4, 2, 3, 1, 0, 2, 4, 3, 1, 0, 1] # should be 14
        # myArr = [0, 0, 1, 2, 4, 4, 4, 3, 1, 0, 0, 0] # should be 0
        myArr = [5, 1, 2, 4, 4, 4, 3, 1, 0, 0, 0] # should be 5

        print(totalRain(myArr))
```
```js
function totalRain(heights) {
  const leftMax = [],
    rightMax = [],
    n = heights.length;
  (leftMax[0] = heights[0]), (rightMax[n - 1] = heights[n - 1]);

  for (let i = 1; i < n; i++) {
    leftMax[i] = Math.max(heights[i], leftMax[i - 1]);
    rightMax[n - 1 - i] = Math.max(heights[n - 1 - i], rightMax[n - i]);
  }
  return leftMax.reduce(
    (water, val, idx) => (water += Math.min(val, rightMax[idx]) - heights[idx]),
    0
  );
}
```
```java
public class MainClass {
    public static void main(String[] args) {
        // Uncomment a different array to see the working on a different array 
        // int[] myArr = {0, 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1, 0, 0}; // should be 6
        // int[] myArr = {0, 0, 1, 0, 2, 4, 4, 4, 2, 3, 1, 0, 2, 4, 3, 1, 0, 1}; // should be 14
        // int[] myArr = {0, 0, 1, 2, 4, 4, 4, 3, 1, 0, 0, 0}; // should be 0
        int[] myArr = {5, 1, 2, 4, 4, 4, 3, 1, 0, 0, 0}; // should be 5

        System.out.println(totalRain(myArr));
    }

    public static int totalRain(int[] heights) {
        if (heights == null || heights.length <= 2) {
            return 0;
        }

        int[] leftMax =  new int[heights.length]; 
        int[] rightMax = new int[heights.length];

        leftMax[0] = heights[0];
        rightMax[heights.length - 1] = heights[heights.length - 1];

        for(int i=1; i<heights.length; i++){
            leftMax[i] = Math.max(heights[i], leftMax[i-1]);
            rightMax[heights.length - 1 - i] = Math.max(heights[heights.length - 1 - i], rightMax[heights.length - i]);
        }

        int water = 0;
        for(int i=0; i<heights.length; i++){
            water += Math.min(leftMax[i], rightMax[i]) - heights[i];
        }
        return water;
    }
}
```
```cpp
#include<bits/stdc++.h>
using namespace std;

int totalRain(vector<int> &height) {
    int n = height.size();
    if(n<=2) return 0;   
    int left[n], right[n];  
    left[0]=height[0];
    right[n-1]=height[n-1];

    for(int i=1;i<n;i++) {
        left[i] = max(height[i], left[i-1]);
        right[n-i-1] = max(height[n-i-1], right[n-i]);
    }
    
    int ans = 0;
    for(int i=0;i<n;i++) {
        ans += min(left[i],right[i])-height[i];
    }
    return ans;
}

int main() {
    // Uncomment a different array to see the working on a different array 
    // vector<int> arr = {0, 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1, 0, 0};
    // vector<int> arr = {0, 0, 1, 0, 2, 4, 4, 4, 2, 3, 1, 0, 2, 4, 3, 1, 0, 1};
    // vector<int> arr = {0, 0, 1, 2, 4, 4, 4, 3, 1, 0, 0, 0};
    vector<int> arr = {5, 1, 2, 4, 4, 4, 3, 1, 0, 0, 0};

    cout<<totalRain(arr)<<endl;
    return 0;
}
```
```csharp
using System;

class Program
{
    public static void Main(string[] args)
    {
        // Uncomment a different array to see the working on a different array 
        // int[] heights = {0, 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1, 0, 0}; 
        // int[] heights = {0, 0, 1, 0, 2, 4, 4, 4, 2, 3, 1, 0, 2, 4, 3, 1, 0, 1};
        // int[] heights = {0, 0, 1, 2, 4, 4, 4, 3, 1, 0, 0, 0};
        int[] heights = {5, 1, 2, 4, 4, 4, 3, 1, 0, 0, 0};

        Console.WriteLine(TotalRain(heights));
    }

     public static int TotalRain(int[] height)
     {
        if (height.Length <= 2)
            return 0;

        int n = height.Length;
        int[] leftMax = new int[n];
        int[] rightMax = new int[n];
        leftMax[0] = height[0];
        rightMax[n - 1] = height[n - 1];

        for (int i = 1; i < n; i++)
        {
            leftMax[i] = Math.Max(height[i], leftMax[i - 1]);
            rightMax[n - 1 - i] = Math.Max(height[n - 1 - i], rightMax[n - 1 - (i - 1)]);
        }

        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            ans += Math.Min(leftMax[i], rightMax[i]) - height[i];
        }

        return ans;
     }
}
```
```go
package main

import (
	"fmt"
)

func max(x, y int) int {
	if x < y {
		return y
	}
	return x
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func totalRain(heights []int) int {
	if len(heights) <= 2 {
		return 0
	}

	leftMax, rightMax := make([]int, len(heights)), make([]int, len(heights))
	leftMax[0], rightMax[len(heights)-1] = heights[0], heights[len(heights)-1]

	for i := 1; i < len(heights); i++ {
		leftMax[i] = max(heights[i], leftMax[i-1])
		rightMax[len(heights)-1-i] = max(heights[len(heights)-1-i], rightMax[len(heights)-i])
	}

	totalRain := 0
	for i := range heights {
		totalRain += min(leftMax[i], rightMax[i]) - heights[i]
	}

	return totalRain
}

func main() {
	// Uncomment a different array to see the working on a different array 
	// heights := []int{0, 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1, 0, 0} 
	// heights := []int{0, 0, 1, 0, 2, 4, 4, 4, 2, 3, 1, 0, 2, 4, 3, 1, 0, 1}
	// heights := []int{0, 0, 1, 2, 4, 4, 4, 3, 1, 0, 0, 0}
	heights := []int{5, 1, 2, 4, 4, 4, 3, 1, 0, 0, 0}

	fmt.Println(totalRain(heights))
}
```

One Pager Cheat Sheet

One Pager Cheat Sheet

  • By solving the Tetris-like problem of determining how much rain a given elevation map with varying bar heights and uniform widths can collect, we can calculate a total answer that fits within the Integer range (< 2^32) in O(n) time and O(1) space.
  • We can find the amount of rainwater trapped in an elevation map by determining the maximum water level at each column, which we can find by taking the minimum value of the maximum height in both directions from any given index.
  • By using the same process from right to left, the two arrays left[] and right[] are generated, which are used to determine the maximum water level at each column.
  • We can calculate the total amount of water at each column/index directly using the left[] and right[] arrays, and sum them up during the iteration.
  • The time complexity is O(n), and the space complexity is also O(n) due to the creation of two additional arrays of the same size as the input array height.
  • We sum up the min of two values calculated from heights, while subtracting heights[i], and check for corner/simplest cases before returning the result.
Open interactive view →