Trapping Rain Water

Problem:

Given n non-negative integers representing an elevation map(block) where the width of each bar is 1, compute how much water it can trap after raining.

Example:

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.

Approach:

This Problem is almost similar to this problem, so we can assume that we can solve this problem using the two-pointers method. But before move on to the two-pointers method, let's try to solve this problem using the forward and backward array methods. 

Previously we have solved another forward and backward array method, named "Maximum Subarray Sum with One Deletion". 

Now, let's try to visualize the problem.

We have to calculate the maximum traping water area, that would be,
    area = Height * Width

=>area = min(left_block_height, right_block_height) - current_height * 1

Width 1, that is given.

Now, why is this happening!

We have to consider every single position.

Suppose we are at position 'x' , if x-1 block is equal to or smaller than 'x' block, then we can't trap water at 'x' position. The same case at x+1 right block hold. Now, suppose the left block is the bigger and the right block, then we can't make an area like (bigger_block - current_block), because from right block water will be overflowed.

Now, How can we calculate the left max and the right max! simple, we will consider two arrays, named Forward array, and another one is a backward array.

Suppose, in 'x' position value of Forward array give a max height consider from 0th index to current index, Backward array will be same but from right.

Complexity, Time Complexity O(n), and Space Complexity O(n), because Forward and backward arrays taking extra memory.

See the code for a better understanding,

See, we illustrate already, if n < 3 then its not possible to trap any water into this, otherwise we have to calculate.

Sorted block also not possible, but we don't need to consider this one.

Then, we are taking only positive height.