Trapping Rain Water

Leet code Link - https://leetcode.com/problems/trapping-rain-water/description/

Complexity - Hard

Description

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

Solution

For each element in the array, we find the maximum level of water it can trap after the rain, which is equal to the minimum of maximum height of bars on both the sides minus its own height.

• Initialize ans=0
• Iterate the array from left to right:
• Initialize left_max=0 and right_max=0
• Iterate from the current element to the beginning of array updating:
• left_max=max(left_max,height[j])
• Iterate from the current element to the end of array updating:
• right_max=max(right_max,height[j])
• Add min(left_max,right_max)−height[i] to ans

class Solution {
    public int trap(int[] height) {
        int ans = 0;
        int size = height.length;
        for (int i = 1; i < size - 1; i++) {
            int left_max = 0, right_max = 0;
            // Search the left part for max bar size
            for (int j = i; j >= 0; j--) {
                left_max = Math.max(left_max, height[j]);
            }
            // Search the right part for max bar size
            for (int j = i; j < size; j++) {
                right_max = Math.max(right_max, height[j]);
            }
            ans += Math.min(left_max, right_max) - height[i];
        }
        return ans;
    }
}

complexity

Time complexity - O(N^2)

Space complexity - O(1)

We can do the above solution in one iteration. We use two pointer technique

class Solution {
    public int trap(int[] height) {
        int i=0; int j=height.length-1;
        int maxarea = 0;
        int leftMax = height[i];
        int rightMax = height[j];
        while(i<j){
            if(leftMax<rightMax){
                i++;
                leftMax = Math.max(leftMax,height[i]);
                maxarea += leftMax-height[i];
            }
            else{
                j--;
                rightMax = Math.max(rightMax,height[j]);
                maxarea += rightMax-height[j];
            }
        }
        return maxarea;
    }
}

time Complexity - O(N)

Space Complexity - O(1)