Problem Definition: 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.

Observations :

As we can observe the rainwater can be saved if it can form a cup pattern means any index has its left side height greater than the current index value and similar on the right side, e.g. for index 2 left greater heights is 1 and in right, it is 2 so water can be stored in index 2. Let us assume that for any index the left max is Lmax and the right max height is Rmax so the maximum rainwater can be saved in that index equal to the difference between min(Lmax, Rmax) and the height of the current index. In the equation for the ith index

R[i] = min (Lmax, Rmax)- height[i]

so what will be the brute force approach? for every index find the left max value and right max value and calculate the difference.

what will be the time complexity?

find left side maximum is O(n) find right side maximum is O(n)

and this need to repeat for n index so the total will be O(n^2)

can we do better than this?

one approach that comes to my mind is calculating prefix maximum and calculating suffix maximum.

so keep track of the left maximum at the current index from the left side, similar to the right maximum from the right side.

what will be the time complexity?

one loop to find the prefix max array which is O(n)

one loop to find the suffix max array which is O(n)

one loop to calculate maximum rainwater need to be stored O(n)

so the total will be O(n)

below is the code

class Solution:
    def trap(self, height: List[int]) -> int:
        sm=0
        if len(height)<3:
            return 0
        l=[0]*len(height)
        l[0]=height[0]
        r=[0]*len(height)
        r[-1]=height[-1]
        for i in range(1,len(height)):
            l[i]=max(l[i-1], height[i])

        for i in range(len(height)-2, -1, -1):
            r[i]=max(r[i+1], height[i])

        for i in range(len(height)):
            k=min(l[i], r[i])-height[i]
            if k>0:
                sm+=k
        return sm