Trapping rain water-coding question asked by DE Shaw, Adobe, Amazon
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.
A vector array
Volume of water trapped
Sample Input 1:
Sample Output 1:
Sample Input 2:
Sample Output 2:
To understand the question, we have drawn a graphical representation for the sample input 1. 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.
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. The heights are stored and the net result is difference of volumes trapped in the two calculations.
Time complexity: O(n)
Space complexity: O(n)
Thanks for Reading
Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.