Analytics Vidhya
Published in

Analytics Vidhya

Trapping Rain Water — Day 11(Python)

Photo by Inge Maria on Unsplash

Today we will be looking at one of the leetcode’s hard tagged questions.

42. Trapping Rain Water

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.

Source: Leetcode

The above elevation map 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.

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Before we look into the solution, let us run through a few examples.

Input: [3, 0, 3]
Output: 3
Input: [3, 0, 1, 0, 3]
Output: 8
Input: [3, 0, 1, 0, 2]
Output: 5

Considering 2 histogram bars at a time, the enclosed space between the bars is the quantity of water. Let us look at the algorithm.

  1. Run the loop until all bars in the array is traversed.

2. Find the max value on the left side of the current bar. Let this value be left_max.

3. Find the max value on the right side of the current bar. Let this value be right_max.

4. Find the minimum between left_max and right_max.

5. Subtract the minimum value from the current bar.

6. If the resulting value is greater than 0, add it to our result. Since we cannot have a negative amount of water being trapped, we ignore it.

class RainWaterTrapper:
def trap(self, height: List[int]) -> int:
total_water = 0
for i in range(1, len(height)-1):
l = max(height[:i])
r = max(height[i+1:])
water = min(l, r) - height[i]
if(water>=0):
total_water += water
return total_water

Complexity analysis.

Time Complexity

We are traversing through the complete array which needs O(N). Additionally, we calculate max values while traversing through the array which takes O(N). Hence the time complexity is O(N²).

Space Complexity

Since we are not using any extra space, space complexity is O(1).

Can we make the algorithm any better?

We keep calculating the max value each time we hit a new bar. Can we keep track of max value beforehand? We can have 2 arrays that keep track of max value for the left side and the right side.

  1. Create an array for left and create an array for right, initialize both as 0.
  2. Run the loop for the left as well as the right of each bar and keep track of the max value and save them in the respective positions.
  3. Once the above steps are completed, run the loop for each bar in the array.
  4. Find the minimum among the left, right, and subtract it from the current bar. Include this quantity in total water.
class RainWaterTrapper:
def trap(self, height: List[int]) -> int:
if height == []:
return 0
left = [0 for i in range(len(height))]
right = [0 for i in range(len(height))]
total_water = 0

left[0] = height[0]
for i in range(1, len(height)):
left[i] = max(left[i-1], height[i])

right[-1] = height[-1]
for i in range(len(height)-2, -1, -1):
right[i] = max(right[i+1], height[i])

for i in range(len(height)):
total_water += min(left[i], right[i]) - height[i]

return total_water

Time Complexity

We are traversing through the complete array which needs O(N).

Space Complexity

We are using 2 extra arrays of size N to store max values, hence space complexity is O(N).

Kindly let me know in case you find any errors in the article. Additionally, I would like to improve my writing skills, any suggestions or comments are welcomed.

--

--

--

Analytics Vidhya is a community of Analytics and Data Science professionals. We are building the next-gen data science ecosystem https://www.analyticsvidhya.com

Recommended from Medium

Cake v2.0.0 RC 1 released

How to make VS Code Beautiful?

Information Architecture — e$aver app

When APIs become real products

Running Docker Inside and Outside of a Jenkins Container, Along With Docker-Compose — a Tiny…

Skipping Intro Cinematic

Life is a journey of twists and turns, peaks and valleys, mountains to climb and oceans to explore.

There Is Only One Web Project

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
Annamariya Tharayil

Annamariya Tharayil

Software Engineer. Find me @ www.linkedin.com/in/annamariya-jt

More from Medium

Elementary operations in PyCUDA

Python Variables and Their Type

Git is not that hard to learn…

Reverse integer