42. Trapping Rain Water

42. Trapping Rain Water

Difficulty: Hard

Related Topics: Array, Two Pointers, Stack

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 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.length0 <= n <= 3 * 10⁴0 <= height[i] <= 10⁵

Solution

Language: Java

class Solution { public int trap(int[] height) { Stack<Integer> storage = new Stack<>(); int curr = 0; int total = 0; while (curr < height.length) { int ele = height[curr]; while (!storage.isEmpty() && ele > height[storage.peek()]) { Integer temp = storage.pop(); if (!storage.isEmpty()) { int left = storage.peek(); total += (Math.min(height[left], ele) - height[temp]) * (curr - left - 1); } else { break; } } storage.push(curr++); } return total; } }

Thought: for trapping rainning water problems, we need to trap them from layer by layer, in this solution, this is solved by poping out every single index from the stack and the height is calculated by the differences that takes into account the height of the floor.

This is a solution in java, time complexity of O(n) and space complexity of O(n)