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


The above elevation map 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. Thanks Marcos for contributing this image!

Example:


Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Difficulty: interview

Starter code:

class Solution:
    def trap(self, height: List[int]) -> int:
        

Solutions:
class Solution:
     def trap(self, height):
         """
         :type height: List[int]
         :rtype: int
         """
         if not height:
             return 0
         result = 0
         left = 0
         right = len(height) - 1
         while left < right:
             if height[left] <= height[right]:
                 tmp = height[left]
                 left += 1
                 while left < right and height[left] <= tmp:
                     result += tmp - height[left]
                     left += 1
             else:
                 tmp = height[right]
                 right -= 1
                 while left < right and height[right] <= tmp:
                     result += tmp - height[right]
                     right -=1 
         return result


class Solution:
     def trap(self, height):
         """
         :type height: List[int]
         :rtype: int
         """
         # if len(height) < 3 :
         #     return 0
         # maxTrap = 0
         # stack=[]
         # i = 0
         # while i < len(height):
         #     if not stack or height[i] <= height[stack[-1]]:
         #         stack.append(i)
         #         i += 1
         #     else :
         #         bot = stack.pop()
         #         trap = 0 if not stack else (min(height[i],height[stack[-1]]) - height[bot] ) * (i-stack[-1]-1)
         #         maxTrap += trap
         #     # print(stack)
         # return maxTrap
         if not height :
             return 0
         left , right = 0 , len(height)-1
         maxLeft,maxRight = height[left],height[right]
         maxTrap = 0
         while left <= right :
             if height[left] <= height[right]:
                 if height[left] > maxLeft :
                     maxLeft = height[left]
                 else :
                     maxTrap += (maxLeft - height[left])
                 left += 1
             else :
                 if height[right] > maxRight:
                     maxRight = height[right]
                 else :
                     maxTrap += (maxRight -height[right])
                 right -= 1
         return maxTrap

class Solution:
     def trap(self, height):
         """
         :type height: List[int]
         :rtype: int
         """
         maxRight = 0
         maxLeft = 0
         left = 0
         right = len(height) - 1
         ret = 0
         while left < right:
             maxRight = max(maxRight, height[right])
             maxLeft = max(maxLeft, height[left])
             if maxLeft > maxRight:
                 ret += maxRight - height[right]
                 right -= 1
             else:
                 ret += maxLeft - height[left]
                 left += 1
         return ret

class Solution:
     def trap(self, height):
         """
         :type height: List[int]
         :rtype: int
         """
         
         # sol1: mono stack
         
         # sol2: heap
         
         l_bounds = []
         lb = float('-inf')
         for h in height:
             lb = max(lb, h)
             l_bounds.append(lb)
             
         water = 0
         rb = float('-inf')
         for lb, h in zip(reversed(l_bounds), reversed(height)):
             rb = max(rb, h)
             water += min(lb, rb) - h
         return water


class Solution:
     def trap(self, height):
         """
         :type height: List[int]
         :rtype: int
         """
         ans = 0
         max_left, max_right = [0]*len(height), [0]*len(height)
         for i in range(1,len(height)):
             max_left[i] = max(max_left[i-1], height[i-1])
         for i in range(len(height)-2,-1,-1):  
             max_right[i] = max(max_right[i+1], height[i+1])
         # 0 added to take care of negative case i.e current step is greater than both max_left and max_right for that step
         for i in range(1,len(height)-1):
             ans += max(min(max_left[i], max_right[i]) - height[i], 0) 
         return ans
                 
             


class Solution:
     def trap(self, barHeights):
         if barHeights == []:
             return 0
         
         numberOfBars = len(barHeights)
 
         leftMaxima = [0 for counter in range(numberOfBars)]
         rightMaxima = [0 for counter in range(numberOfBars)]
 
         leftMaxima[0] = barHeights[0]
         for counter in range(1, numberOfBars):
             leftMaxima[counter] = max(leftMaxima[counter-1], barHeights[counter])
 
         rightMaxima[numberOfBars-1] = barHeights[numberOfBars-1]
         for counter in range(numberOfBars-2, -1, -1):
             rightMaxima[counter] = max(rightMaxima[counter+1], barHeights[counter])
 
         waterTrapped = 0
         for counter in range(0, numberOfBars):
             waterTrapped += (min(leftMaxima[counter], rightMaxima[counter]) - barHeights[counter])
 
         return waterTrapped


class Solution:
     '''Complexity O(n)'''
 
     def trap(self, height):
         n = len(height)
         l, r, water, minHeight = 0, n - 1, 0, 0
 
         while l < r:
             while l < r and height[l] <= minHeight:
                 water += minHeight - height[l]
                 l += 1
 
             while r > l and height[r] <= minHeight:
                 water += minHeight - height[r]
                 r -= 1
 
             minHeight = min(height[l], height[r])
 
         return water

class Solution:
     def trap(self, height):
         """
         :type height: List[int]
         :rtype: int
         """
         left, right = 0, len(height) - 1
         result = 0
         while left < right:
             mh = min(height[left], height[right])
             if height[left]< height[right]:
                 left = left + 1
                 while height[left] <= mh and left < right:
                     result = result + mh - height[left]
                     left = left + 1
             else:
                 right = right - 1
                 while height[right] <= mh and left < right:
                     result = result + mh - height[right]
                     right = right - 1
                     
         return result

class Solution:
     def trap(self, height):
         """
         :type height: List[int]
         :rtype: int
         """
         ans = 0
         max_left, max_right = [0]*len(height), [0]*len(height)
         for i in range(1,len(height)):
             max_left[i] = max(max_left[i-1], height[i-1])
         for i in range(len(height)-2,-1,-1):  
             max_right[i] = max(max_right[i+1], height[i+1])
         # 0 added to take care of negative case i.e current step is greater than both max_left and max_right for that step
         for i in range(1,len(height)-1):
             ans += max(min(max_left[i], max_right[i]) - height[i], 0) 
         return ans
                 
             


class Solution:
     def trap(self, height):
         """
         :type height: List[int]
         :rtype: int
         """
         leftmaxes = []
         rightmaxes = []
         
         maximum = 0
         for i in range(len(height)):
             maximum = max(maximum, height[i])
             leftmaxes.append(maximum)
             
             
         maximum = 0
         for i in range(len(height)):
             maximum = max(maximum, height[len(height) - i - 1])
             rightmaxes.append(maximum)
         
         water = 0
         
         print(leftmaxes)
         print(rightmaxes)
         
         for i in range(len(height)):
             trappable = min(leftmaxes[i], rightmaxes[-i-1])
             if(trappable > height[i]):
                 water += trappable - height[i]
         
         return water


class Solution:
     def trap(self, height):
         """
         :type height: List[int]
         :rtype: int
         """
         
         length = len(height)
         if(length == 0):
             return 0
         maxLeft = [0] * length
         maxRight = [0] * length
         result = 0
         maxLeft[0] = height[0]
         maxRight[length - 1] = height[length - 1]
         for i in range(1,length):
             maxLeft[i] = max(maxLeft[i - 1], height[i])
         for i in reversed(list(range(0, length - 1))):
             maxRight[i] = max(maxRight[i + 1], height[i])
         for i in range(length):
             result += min(maxLeft[i], maxRight[i]) - height[i]
         return result
 
                     
             
             


class Solution:
     def trap(self, height):
         """
         :type height: List[int]
         :rtype: int
         """
         # find valleys
         N = len(height)
         valleys = [] # a list of [left, right] (not inclusive) bounds of local minimum
         i = 0
         while i < N-1:
             # first go uphills and then down hills until flat or up hills, this is a potential left bound of a valley
             while i < N-1 and height[i] <= height[i+1]: i += 1
             while i < N-1 and height[i] > height[i+1]: i += 1 # ensures height[i] <= height[i+1] unless out of bounds
             j = i
             while j < N-1 and height[j] == height[j+1]: j += 1 # go through the range of the potential bottom of the valley
             if j < N-1 and height[j] < height[j+1]: valleys.append([i-1,j+1]) # store a confirmed valley with bottom [i:j+1]
             i = j
         
         # fill water into each valley
         total_water = 0
         further_valleys = [] # list of potential valley to merge as those whose left side is higher after water filll
         k = 0
         if valleys: # initialize
             l = valleys[k][0]
             r = valleys[k][1]
             old_level = height[l+1]
         while k < len(valleys):
             # record bottom level
             water = 0
             while l >= 0 and r < N and height[l] >= height[l+1] and height[r-1] <= height[r]: # both sides rising
                 # fill water at [l+1:r]
                 new_level = min(height[l], height[r])
                 water += (new_level - old_level) * (r - l - 1)
                 old_level = new_level
                 # advance to the next level in the valley
                 if l >= 0 and r < N:
                     # rise only the lower side
                     if height[l] == height[r]:
                         l -= 1
                         r += 1
                     elif height[l] < height[r]: l -= 1
                     else: r += 1
                     # make sure level rises
                     while l >= 0 and height[l] == height[l+1]: l -= 1
                     while r < N and height[r-1] == height[r]: r += 1
             total_water += water
             
             # l == -1 or r == N or height[l] < height[l+1] or height[r-1] > height[r]
             if l >= 0 and r < N:
                 if height[l] > height[l+1]: # further rise is possible after the next valley is filled
                     further_valleys.append([l,r])
                 elif further_valleys and height[further_valleys[-1][1]-1] == height[l+1]: # merge two valleys
                     old_level = height[l+1] # water already filled to this level
                     l = further_valleys[-1][0]
                     further_valleys.pop()
                     continue # fill the merged valley before moving on
             
             # fill the next valley
             k += 1
             if k < len(valleys):
                 l = valleys[k][0]
                 r = valleys[k][1]
                 old_level = height[l+1]
             
         return total_water

class Solution:
     
     def get_empty_per_level(self, height, level):
         print(("Level: ", level))
         block_start = 0
         n = len(height)
         while block_start < n and height[block_start] < level:
             block_start += 1
             
         if block_start == n:   
             print("No start")
             return n
         
         block_end = n - 1
         while block_end > block_start and height[block_end] < level:
             block_end -= 1
             
         if block_end == block_start:
             print("No end")
             return n - 1
         
         print("Some value")
         return n - (block_end - block_start + 1)
     
     def trap(self, height):
         """
         :type height: List[int]
         :rtype: int
         """
         
         if not height or len(height) == 0:
             return 0
         
         levels = set(height)              
         levels = list(levels)
         
         if 0 in levels:
             levels.remove(0)
             
         levels.sort()
         
         if len(levels) == 0:
             return 0
                 
         max_level = max(height)
         total_count = sum([max_level - item for item in height])                
             
         prev_level = levels.pop(0)
         missing_water_per_level = self.get_empty_per_level(height, prev_level)                
         total_count -= prev_level * missing_water_per_level                                
         for level in levels:
             missing_water_per_level = self.get_empty_per_level(height, level)                                
             multi_level_count = (level - prev_level) * missing_water_per_level
             total_count -= multi_level_count                        
             #print("Level: ", level, " count after: ", total_count, "missing water: ", missing_water_per_level)
             
             prev_level = level
             
         return total_count