In a Meta-style coding interview, you are given an array height where each element represents the height of a vertical bar in an elevation map. Return the total amount of rain water that can be trapped after raining.
height, a list of non-negative integersWater above index i is determined by the shorter of the tallest bar to its left and right, minus height[i], if that value is positive.
Example 1
height = [0,1,0,2,1,0,1,3,2,1,2,1]6Example 2
height = [4,2,0,3,2,5]91 <= len(height) <= 2 * 10^40 <= height[i] <= 10^5Aim for a linear-time solution. A brute-force approach that scans left and right for every index is correct but too slow for large inputs.
height = [0,1,0,2,1,0,1,3,2,1,2,1]Output6WhyThe valleys between taller bars trap a total of 6 units of water.height = [4,2,0,3,2,5]Output9WhyThe left wall of height 4 and right wall of height 5 trap water across the middle bars for a total of 9.height = [3,0,2,0,4]Output7WhyWater is trapped above indices 1, 2, and 3 with amounts 3, 1, and 3 respectively.1 <= len(height) <= 2 * 10^40 <= height[i] <= 10^5Return the total trapped water as an integerdef trap_rain_water(height):