# Question

Formatted question description: https://leetcode.ca/all/42.html

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 <= 2 * 104
• 0 <= height[i] <= 105

# Algorithm - firstly finding the max height

Based on Dynamic Programming, maintaining a one-dimensional dp array, this DP algorithm needs to traverse the array two passes.

The first pass stores the maximum value of the left position of i in dp[i], and then starts the second pass to traverse the array.

In the second traversal, find the maximum value on the right, and then compare it with the maximum on the left to take the smaller value, and compare it with the current value A[i]. If it is greater than the current value, store the difference in the result.

# Algorithm 2 - not finding the max height

If height has length 0, then return 0.

Loop over height in both directions and use two arrays leftMax and rightMax to store maximum height in both directions. Each element in the array leftMax represents the maximum height in the subarray from the leftmost index to the current index. Each element in the array rightMax represents the maximum height in the subarray from the current index to the rightmost index.

For each index i, the maximum amount of water trapped at the index is Math.min(leftMax[i], rightMax[i]) - height[i]. Thus the total amount of water trapped can be obtained.

# Code

• public class Trapping_Rain_Water {

public static void main(String[] args) {
Trapping_Rain_Water out = new Trapping_Rain_Water();
Solution_local_minimum s = out.new Solution_local_minimum();

System.out.println(s.trap(new int[]{5,2,1,2,1,5}));
}

// The short board effect, the storage capacity is related to the short board of the bucket.
// Find the longest slab in the height array, and then iterate from both ends to the long slab. When encountering a shorter one, find the storage capacity, and when encountering a longer one, update the edge.
public class Solution_optimize {
public int trap(int[] height) {

if (height == null || height.length == 0)     return 0;

int sum = 0;
int maxind = 0;
int max = Integer.MIN_VALUE;

// find max index
for (int i = 0; i < height.length; i++) {
if (height[i] > max) {
max = height[i];
maxind = i;
}
}

// left
int leftmax = height[0];
for (int i = 1; i < maxind; i++) {

if (leftmax < height[i]) {
leftmax = height[i];
}

sum += leftmax - height[i];
}

// right
int rightmax = height[height.length - 1];
for (int i = height.length - 2; i > maxind; i--) {
if (rightmax < height[i]) {
rightmax = height[i];
}

sum += rightmax - height[i];
}

return sum;
}
}

// local minimum solution is NOT doable. like [5,2,1,2,1,5], there are 2 local minimums with each holding 1 water
// but they are just part of a global minimum
class Solution_local_minimum {

public int trap(int[] height) {

// for each position, probe to left and right, find local minimum

if (height == null || height.length == 0)     return 0;

int sum = 0;

int i = 1; // index=0 or index=length-1 will not be a local min, since nothing on its left to hold water
while (i < height.length - 1) {

// only process local min index
if (height[i] < height[i - 1] && height[i] < height[i + 1]) {

int left = i - 1;
while (left - 1 >= 0 && height[left] < height[left - 1]) {
left--;
}

int right = i + 1;
while (right + 1 < height.length && height[right] < height[right + 1]) {
right++;
}

// now find its highest bar on both sides
int lower = Math.min(height[left], height[right]);

while (left < right) {

if (height[left] < lower) {
sum += lower - height[left];
}

left ++;
}

// update pointer to search next local minimum
i = right;

} else {
i++;
}
}

return sum;
}

}

}

//////

class Solution_notFindingMaxHeight {
public int trap(int[] height) {
if (height == null || height.length == 0)
return 0;
int length = height.length;
int[] leftMax = new int[length]; // leftMax represents the maximum height in the subarray from the leftmost index to the current index
int[] rightMax = new int[length]; // rightMax represents the maximum height in the subarray from the current index to the rightmost index
leftMax[0] = height[0];
for (int i = 1; i < length; i++)
leftMax[i] = Math.max(height[i], leftMax[i - 1]);
rightMax[length - 1] = height[length - 1];
for (int i = length - 2; i >= 0; i--)
rightMax[i] = Math.max(height[i], rightMax[i + 1]);
int amount = 0;
for (int i = 0; i < length; i++)
amount += Math.min(leftMax[i], rightMax[i]) - height[i];
return amount;
}
}

//////

class Solution {
public int trap(int[] height) {
int n = height.length;
if (n < 3) {
return 0;
}

int[] lmx = new int[n];
int[] rmx = new int[n];
lmx[0] = height[0];
rmx[n - 1] = height[n - 1];
for (int i = 1; i < n; ++i) {
lmx[i] = Math.max(lmx[i - 1], height[i]);
rmx[n - 1 - i] = Math.max(rmx[n - i], height[n - i - 1]);
}

int res = 0;
for (int i = 0; i < n; ++i) {
res += Math.min(lmx[i], rmx[i]) - height[i];
}
return res;
}
}

• // OJ: https://leetcode.com/problems/trapping-rain-water/
// Time: O(N)
// Space: O(N)
class Solution {
public:
int trap(vector<int>& A) {
int N = A.size(), ans = 0;
vector<int> left(N, 0), right(N, 0);
for (int i = 1; i < N; ++i) left[i] = max(left[i - 1], A[i - 1]);
for (int i = N - 2; i >= 0; --i) right[i] = max(right[i + 1], A[i + 1]);
for (int i = 1; i < N - 1; ++i) ans += max(0, min(left[i], right[i]) - A[i]);
return ans;
}
};

• class Solution:
def trap(self, height: List[int]) -> int:
n = len(height)
if n < 3:
return 0

lmx = [height[0]] * n
rmx = [height[n - 1]] * n
for i in range(1, n):
lmx[i] = max(lmx[i - 1], height[i]) # i self compare
rmx[n - 1 - i] = max(rmx[n - i], height[n - 1 - i])

# no negative, worst is, min(left,right) is itself
return sum( min(lmx[i], rmx[i]) - height[i] for i in range(n) )

######

class Solution: # zip
def trap(self, height: List[int]) -> int:
n = len(height)
left = [height[0]] * n
right = [height[-1]] * n
for i in range(1, n):
left[i] = max(left[i - 1], height[i])
right[n - i - 1] = max(right[n - i], height[n - i - 1])
return sum(min(l, r) - h for l, r, h in zip(left, right, height))

######

class Solution: # find the highest bar first
def trap(self, height: List[int]) -> int:
if not height:
return 0

total_water = 0
max_index = 0
max_height = float('-inf')

# Find the index of the maximum height
for i in range(len(height)):
if height[i] > max_height:
max_height = height[i]
max_index = i

# Calculate water trapped on the left side of the maximum height
left_max = height[0]
for i in range(1, max_index):
if left_max < height[i]:
left_max = height[i]
total_water += left_max - height[i]

# Calculate water trapped on the right side of the maximum height
right_max = height[-1]
for i in range(len(height) - 2, max_index, -1):
if right_max < height[i]:
right_max = height[i]
total_water += right_max - height[i]


• func trap(height []int) int {
n := len(height)
if n < 3 {
return 0
}

lmx, rmx := make([]int, n), make([]int, n)
lmx[0], rmx[n-1] = height[0], height[n-1]
for i := 1; i < n; i++ {
lmx[i] = max(lmx[i-1], height[i])
rmx[n-1-i] = max(rmx[n-i], height[n-1-i])
}

res := 0
for i := 0; i < n; i++ {
res += min(lmx[i], rmx[i]) - height[i]
}
return res
}

func max(a, b int) int {
if a > b {
return a
}
return b
}

func min(a, b int) int {
if a < b {
return a
}
return b
}

• function trap(height: number[]): number {
let ans = 0;
let left = 0,
right = height.length - 1;
let maxLeft = 0,
maxRight = 0;
while (left < right) {
if (height[left] < height[right]) {
// move left
if (height[left] >= maxLeft) {
maxLeft = height[left];
} else {
ans += maxLeft - height[left];
}
++left;
} else {
// move right
if (height[right] >= maxRight) {
maxRight = height[right];
} else {
ans += maxRight - height[right];
}
--right;
}
}
return ans;
}


• public class Solution {
public int Trap(int[] height) {
int n = height.Length;
int[] left = new int[n];
int[] right = new int[n];
left[0] = height[0];
right[n - 1] = height[n - 1];
for (int i = 1; i < n; ++i) {
left[i] = Math.Max(left[i - 1], height[i]);
right[n - i - 1] = Math.Max(right[n - i], height[n - i - 1]);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans += Math.Min(left[i], right[i]) - height[i];
}
return ans;
}
}

• impl Solution {
pub fn trap(height: Vec<i32>) -> i32 {
let n = height.len();
let mut left: Vec<i32> = vec![0; n];
let mut right: Vec<i32> = vec![0; n];

left[0] = height[0];
right[n - 1] = height[n - 1];

// Initialize the left & right vector
for i in 1..n {
left[i] = std::cmp::max(left[i - 1], height[i]);
right[n - i - 1] = std::cmp::max(right[n - i], height[n - i - 1]);
}

let mut ans = 0;

// Calculate the ans
for i in 0..n {
ans += std::cmp::min(left[i], right[i]) - height[i];
}

ans
}
}

• class Solution {
/**
* @param integer[] $height * @return integer */ function trap($height) {
$n = count($height);

if ($n == 0) { return 0; }$left = 0;
$right =$n - 1;
$leftMax = 0;$rightMax = 0;
$ans = 0; while ($left < $right) { if ($height[$left] <$height[$right]) { if ($height[$left] >$leftMax) {
$leftMax =$height[$left]; } else {$ans += $leftMax -$height[$left]; }$left++;
} else {
if ($height[$right] > $rightMax) {$rightMax = $height[$right];
} else {
$ans +=$rightMax - $height[$right];
}
$right--; } } return$ans;
}
}