Solution
Approach 1: Brute force
Intuition
Do as directed in question. 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.
Algorithm
 Initialize
 Iterate the array from left to right:
 Initialize and
 Iterate from the current element to the beginning of array updating:
 Iterate from the current element to the end of array updating:
 Add to
Complexity Analysis

Time complexity: . For each element of array, we iterate the left and right parts.

Space complexity: extra space.
Approach 2: Dynamic Programming
Intuition
In brute force, we iterate over the left and right parts again and again just to find the highest bar size upto that index. But, this could be stored. Voila, dynamic programming.
The concept is illustrated as shown:
Algorithm
 Find maximum height of bar from the left end upto an index i in the array .
 Find maximum height of bar from the right end upto an index i in the array .
 Iterate over the array and update ans:
 Add to
Complexity analysis

Time complexity: .
 We store the maximum heights upto a point using 2 iterations of each.
 We finally update using the stored values in .

Space complexity: extra space.
 Additional space for and arrays than in Approach 1.
 Additional space for and arrays than in Approach 1.
Approach 3: Using stacks
Intuition
Instead of storing the largest bar upto an index as in Approach 2, we can use stack to keep track of the bars that are bounded by longer bars and hence, may store water. Using the stack, we can do the calculations in only one iteration.
We keep a stack and iterate over the array. We add the index of the bar to the stack if bar is smaller than or equal to the bar at top of stack, which means that the current bar is bounded by the previous bar in the stack. If we found a bar longer than that at the top, we are sure that the bar at the top of the stack is bounded by the current bar and a previous bar in the stack, hence, we can pop it and add resulting trapped water to .
Algorithm
 Use stack to store the indices of the bars.
 Iterate the array:
 While stack is not empty and
 It means that the stack element can be popped. Pop the top element as .
 Find the distance between the current element and the element at top of stack, which is to be filled.
 Find the bounded height
 Add resulting trapped water to answer
 Push current index to top of the stack
 Move to the next position
 While stack is not empty and
Complexity analysis
 Time complexity: .
 Single iteration of in which each bar can be touched at most twice(due to insertion and deletion from stack) and insertion and deletion from stack takes time.
 Space complexity: . Stack can take upto space in case of stairslike or flat structure.
Approach 4: Using 2 pointers
Intuition
As in Approach 2, instead of computing the left and right parts seperately, we may think of some way to do it in one iteration. From the figure in dynamic programming approach, notice that as long as (from element 0 to 6), the water trapped depends upon the left_max, and similar is the case when (from element 8 to 11). So, we can say that if there is a larger bar at one end (say right), we are assured that the water trapped would be dependant on height of bar in current direction (from left to right). As soon as we find the bar at other end (right) is smaller, we start iterating in opposite direction (from right to left). We must maintain and during the iteration, but now we can do it in one iteration using 2 pointers, switching between the two.
Algorithm
 Initialize pointer to 0 and pointer to size1
 While , do:
 If is smaller than
 If , update
 Else add to
 Add 1 to .
 Else
 If , update
 Else add to
 Subtract 1 from .
 If is smaller than
Refer the example for better understanding: !?!../Documents/42/42_trapping_rain_water.json:1000,662!?!
Complexity analysis
 Time complexity: . Single iteration of .
 Space complexity: extra space. Only constant space required for , , and .