Monotonic Array / TwoPointer :Trapping Rain Water: Most Asked !!

Day 16/75 :

Problem : Trapping Rain Water -(Hard)

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.

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.        

Approach1: Monotonic Stack Approach ( leftMax and RightMax)

Monotonic Stack: Stack which maintains , element is specific order. (ascending/descending)

Here, We maintain two different Arrays for leftMax and rightMax,at each position.

1. Traverse left to right and find leftMax of each position ,store it in leftMax array.
2. Now, traverse right to left and find rightMaxof each position ,store it in rightMax array.
3. Now,Traverse again and calculate waterlevel at each position and return totalTrapped Water.

Code:

Time Complexity : O(n)

Space Complexity : O(n) , As we maintain two different array for leftMax and rightMax.

Approach 2: Two Pointer

We bascically maintains two pointers left (assigned to leftMost height)and right(assigned to rightMost height).

1. Loop, till left less than equal to right.
2. If height of left/right is greater than leftMax/ rightMax. Update leMax/rightMax and shift left and right pointer accordingly.
3. But if ,leftMax/ rightMax is greater than height of left/right. Then simply ,calculate WaterLevel of that position. i.e ( waterlevel += min(lMax,rMax)-height[left/right].
4. Return Trapped waterLevel.

Code:

Time Complexity: O(n)

Space Complexity: O(1) .As no extra space is used.