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

Problem Statement:

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.

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.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store