42. Trapping rain water

42_solution1_prefix_suffix.c

#include <stdlib.h>

int trap(int *height, int heightSize) {
    if (heightSize == 0) {
        return 0;
    }

    int *leftMax = malloc(heightSize * sizeof(int));
    int *rightMax = malloc(heightSize * sizeof(int));

    leftMax[0] = height[0];
    for (int i = 1; i < heightSize; i++) {
        leftMax[i] = height[i] > leftMax[i - 1] ? height[i] : leftMax[i - 1];
    }

    rightMax[heightSize - 1] = height[heightSize - 1];
    for (int i = heightSize - 2; i >= 0; i--) {
        rightMax[i] = height[i] > rightMax[i + 1] ? height[i] : rightMax[i + 1];
    }

    int total = 0;
    for (int i = 0; i < heightSize; i++) {
        int level = leftMax[i] < rightMax[i] ? leftMax[i] : rightMax[i];
        total += level - height[i];
    }

    free(leftMax);
    free(rightMax);

    return total;
}

42_solution2_two_pointers.c

int trap(int *height, int heightSize) {
    if (heightSize == 0) {
        return 0;
    }

    int left = 0, right = heightSize - 1;
    int leftMax = height[left], rightMax = height[right];
    int total = 0;

    while (left < right) {
        if (leftMax < rightMax) {
            left++;
            if (height[left] > leftMax) leftMax = height[left];
            total += leftMax - height[left];
        } else {
            right--;
            if (height[right] > rightMax) rightMax = height[right];
            total += rightMax - height[right];
        }
    }

    return total;
}

42_solution3_monotonic_stack.c

#include <stdlib.h>

int trap(int *height, int heightSize) {
    if (heightSize == 0) {
        return 0;
    }

    int *stack = malloc(heightSize * sizeof(int));
    int top = 0;
    int total = 0;

    for (int i = 0; i < heightSize; i++) {
        while (top > 0 && height[i] > height[stack[top - 1]]) {
            int bottom = stack[--top];

            if (top == 0) {
                break;
            }

            int left = stack[top - 1];
            int width = i - left - 1;
            int limit = height[left] < height[i] ? height[left] : height[i];
            total += width * (limit - height[bottom]);
        }

        stack[top++] = i;
    }

    free(stack);

    return total;
}

42_solution1_prefix_suffix.cpp

#include <vector>
using namespace std;
class Solution {
public:
  int trap(vector<int> &height) {
    if (height.empty()) {
      return 0;
    }

    int n = height.size();
    vector<int> leftMax(n), rightMax(n);

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

    rightMax[n - 1] = height[n - 1];
    for (int i = n - 2; i >= 0; i--) {
      rightMax[i] = max(rightMax[i + 1], height[i]);
    }

    int total = 0;
    for (int i = 0; i < n; i++) {
      total += min(leftMax[i], rightMax[i]) - height[i];
    }

    return total;
  }
};

42_solution2_two_pointers.cpp

#include <vector>
using namespace std;
class Solution {
public:
  int trap(vector<int> &height) {
    if (height.empty()) {
      return 0;
    }

    int left = 0, right = height.size() - 1;
    int leftMax = height[left], rightMax = height[right];
    int total = 0;

    while (left < right) {
      if (leftMax < rightMax) {
        left++;
        leftMax = max(leftMax, height[left]);
        total += leftMax - height[left];
      } else {
        right--;
        rightMax = max(rightMax, height[right]);
        total += rightMax - height[right];
      }
    }

    return total;
  }
};

42_solution3_monotonic_stack.cpp

#include <stack>
#include <vector>
using namespace std;
class Solution {
public:
  int trap(vector<int> &height) {
    stack<int> st;
    int total = 0;

    for (int i = 0; i < (int)height.size(); i++) {
      while (!st.empty() && height[i] > height[st.top()]) {
        int bottom = st.top();
        st.pop();

        if (st.empty()) {
          break;
        }

        int left = st.top();
        int width = i - left - 1;
        int depth = min(height[left], height[i]) - height[bottom];
        total += width * depth;
      }

      st.push(i);
    }

    return total;
  }
};

42_solution1_prefix_suffix.go

package solution

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

    leftMax := make([]int, n)
    rightMax := make([]int, n)

    leftMax[0] = height[0]
    for i := 1; i < n; i++ {
        leftMax[i] = leftMax[i-1]
        if height[i] > leftMax[i] {
            leftMax[i] = height[i]
        }
    }

    rightMax[n-1] = height[n-1]
    for i := n - 2; i >= 0; i-- {
        rightMax[i] = rightMax[i+1]
        if height[i] > rightMax[i] {
            rightMax[i] = height[i]
        }
    }

    total := 0
    for i := 0; i < n; i++ {
        level := leftMax[i]
        if rightMax[i] < level {
            level = rightMax[i]
        }
        total += level - height[i]
    }

    return total
}

42_solution2_two_pointers.go

package solution

func trap(height []int) int {
    if len(height) == 0 {
        return 0
    }

    left, right := 0, len(height)-1
    leftMax, rightMax := height[left], height[right]
    total := 0

    for left < right {
        if leftMax < rightMax {
            left++
            if height[left] > leftMax {
                leftMax = height[left]
            }
            total += leftMax - height[left]
        } else {
            right--
            if height[right] > rightMax {
                rightMax = height[right]
            }
            total += rightMax - height[right]
        }
    }

    return total
}

42_solution3_monotonic_stack.go

package solution

func trap(height []int) int {
    stack := []int{}
    total := 0

    for i, h := range height {
        for len(stack) > 0 && h > height[stack[len(stack)-1]] {
            bottom := stack[len(stack)-1]
            stack = stack[:len(stack)-1]

            if len(stack) == 0 {
                break
            }

            left := stack[len(stack)-1]
            width := i - left - 1
            limit := height[left]
            if h < limit {
                limit = h
            }
            total += width * (limit - height[bottom])
        }

        stack = append(stack, i)
    }

    return total
}

42_solution1_prefix_suffix.java

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

        int[] leftMax = new int[n];
        int[] rightMax = new int[n];

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

        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }

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

        return total;
    }
}

42_solution2_two_pointers.java

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

        int left = 0, right = height.length - 1;
        int leftMax = height[left], rightMax = height[right];
        int total = 0;

        while (left < right) {
            if (leftMax < rightMax) {
                left++;
                leftMax = Math.max(leftMax, height[left]);
                total += leftMax - height[left];
            } else {
                right--;
                rightMax = Math.max(rightMax, height[right]);
                total += rightMax - height[right];
            }
        }

        return total;
    }
}

42_solution3_monotonic_stack.java

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int trap(int[] height) {
        Deque<Integer> stack = new ArrayDeque<>();
        int total = 0;

        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int bottom = stack.pop();

                if (stack.isEmpty()) break;

                int left = stack.peek();
                int width = i - left - 1;
                int depth = Math.min(height[left], height[i]) - height[bottom];
                total += width * depth;
            }

            stack.push(i);
        }

        return total;
    }
}

42_solution1_prefix_suffix.js

class Solution {
  trap(height) {
    const n = height.length;
    if (n === 0) return 0;

    const leftMax = new Array(n);
    const rightMax = new Array(n);

    leftMax[0] = height[0];
    for (let i = 1; i < n; i++) {
      leftMax[i] = Math.max(leftMax[i - 1], height[i]);
    }

    rightMax[n - 1] = height[n - 1];
    for (let i = n - 2; i >= 0; i--) {
      rightMax[i] = Math.max(rightMax[i + 1], height[i]);
    }

    let total = 0;
    for (let i = 0; i < n; i++) {
      total += Math.min(leftMax[i], rightMax[i]) - height[i];
    }

    return total;
  }
}

42_solution2_two_pointers.js

class Solution {
  trap(height) {
    if (height.length === 0) return 0;

    let left = 0;
    let right = height.length - 1;
    let leftMax = height[left];
    let rightMax = height[right];
    let total = 0;

    while (left < right) {
      if (leftMax < rightMax) {
        left++;
        leftMax = Math.max(leftMax, height[left]);
        total += leftMax - height[left];
      } else {
        right--;
        rightMax = Math.max(rightMax, height[right]);
        total += rightMax - height[right];
      }
    }

    return total;
  }
}

42_solution3_monotonic_stack.js

class Solution {
  trap(height) {
    const stack = [];
    let total = 0;

    for (let i = 0; i < height.length; i++) {
      while (stack.length > 0 && height[i] > height[stack[stack.length - 1]]) {
        const bottom = stack.pop();

        if (stack.length === 0) break;

        const left = stack[stack.length - 1];
        const width = i - left - 1;
        const depth = Math.min(height[left], height[i]) - height[bottom];
        total += width * depth;
      }

      stack.push(i);
    }

    return total;
  }
}

42_solution1_prefix_suffix.py

class Solution:
    def trap(self, height: list[int]) -> int:
        if not height:
            return 0

        n = len(height)
        left_max = [0] * n
        right_max = [0] * n

        left_max[0] = height[0]
        for i in range(1, n):
            left_max[i] = max(left_max[i - 1], height[i])

        right_max[n - 1] = height[n - 1]
        for i in range(n - 2, -1, -1):
            right_max[i] = max(right_max[i + 1], height[i])

        total = 0
        for i in range(n):
            total += min(left_max[i], right_max[i]) - height[i]

        return total

42_solution2_two_pointers.py

class Solution:
    def trap(self, height: list[int]) -> int:
        if not height:
            return 0

        left, right = 0, len(height) - 1
        left_max, right_max = height[left], height[right]
        total = 0

        while left < right:
            if left_max < right_max:
                left += 1
                left_max = max(left_max, height[left])
                total += left_max - height[left]
            else:
                right -= 1
                right_max = max(right_max, height[right])
                total += right_max - height[right]

        return total

42_solution3_monotonic_stack.py

class Solution:
    def trap(self, height: list[int]) -> int:
        stack = []
        total = 0

        for i, h in enumerate(height):
            while stack and h > height[stack[-1]]:
                bottom = stack.pop()

                if not stack:
                    break

                left = stack[-1]
                width = i - left - 1
                depth = min(height[left], h) - height[bottom]
                total += width * depth

            stack.append(i)

        return total

42_solution1_prefix_suffix.rs

struct Solution;

impl Solution {
    fn trap(height: Vec<i32>) -> i32 {
        let n = height.len();
        if n == 0 {
            return 0;
        }

        let mut left_max = vec![0; n];
        let mut right_max = vec![0; n];

        left_max[0] = height[0];
        for i in 1..n {
            left_max[i] = left_max[i - 1].max(height[i]);
        }

        right_max[n - 1] = height[n - 1];
        for i in (0..n - 1).rev() {
            right_max[i] = right_max[i + 1].max(height[i]);
        }

        let mut total = 0;
        for i in 0..n {
            total += left_max[i].min(right_max[i]) - height[i];
        }

        total
    }
}

42_solution2_two_pointers.rs

struct Solution;

impl Solution {
    fn trap(height: Vec<i32>) -> i32 {
        if height.is_empty() {
            return 0;
        }

        let mut left = 0usize;
        let mut right = height.len() - 1;
        let mut left_max = height[left];
        let mut right_max = height[right];
        let mut total = 0;

        while left < right {
            if left_max < right_max {
                left += 1;
                left_max = left_max.max(height[left]);
                total += left_max - height[left];
            } else {
                right -= 1;
                right_max = right_max.max(height[right]);
                total += right_max - height[right];
            }
        }

        total
    }
}

42_solution3_monotonic_stack.rs

struct Solution;

impl Solution {
    fn trap(height: Vec<i32>) -> i32 {
        let mut stack: Vec<usize> = Vec::new();
        let mut total = 0;

        for i in 0..height.len() {
            while let Some(&top) = stack.last() {
                if height[i] <= height[top] {
                    break;
                }

                let bottom = stack.pop().unwrap();

                match stack.last() {
                    None => break,
                    Some(&left) => {
                        let width = (i - left - 1) as i32;
                        let depth = height[left].min(height[i]) - height[bottom];
                        total += width * depth;
                    }
                }
            }

            stack.push(i);
        }

        total
    }
}