Community

Start a Thread


Notifications
Subscribe You’re not receiving notifications from this thread.

Trapping Rain Water (Main Thread)

Here is the interview question prompt, presented for reference.

Suppose you are given an elevation map composed of bars of different heights. You can assume that each bar has the same width. Can you figure out how much rain it will collect?

The Problem Setting

There can be different ways of representing an elevation map. We'll consider the simplest method of using a one dimensional array of non-negative numbers to represent the height at different places. The goal is to find out how much rain can be trapped when given an elevation map. The figure below shows various elevation maps and the units of rain water they can catch.

Constraints

  • Length of the array <= 100000
  • Values in the array >=0
  • The final answer would fit in the Integer range(< 2^32)
  • Expected time complexity : O(n)
  • Expected space complexity : O(1)

You can see the full challenge with visuals at this link.

Challenges • Asked over 3 years ago by Jake from AlgoDaily

Jake from AlgoDaily Commented on Nov 30, 2017:

This is the main discussion thread generated for Trapping Rain Water.

bsanneh Commented on Jan 02, 2021:

There are no test cases and the environment does not support python

Jake from AlgoDaily Commented on Jan 02, 2021:

Thanks for the heads up and sorry for the miss! Added to the queue for the team to address, will update when resolved.

bsanneh Commented on Jan 02, 2021:

Thank you

Jake from AlgoDaily Commented on Jan 04, 2021:

Updated and resolved :-)