Trapping rain water-coding question asked by DE Shaw, Adobe, Amazon

Problem Statement:

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 Format:

A vector array

Output Format:

Volume of water trapped

Sample Input 1:

[0,1,0,2,1,0,1,3,2,1,2,1]

Sample Output 1:

6

Sample Input 2:

[4,2,0,3,2,5]

Sample Output 2:

9

Explanation:

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.

Approach:

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)

Code:

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.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.