Trapping Rainwater Problem | Leetcode | Rain water trapping problem | DSA-One Course #16 (2023)

Introduction

Hey guys, In this video we're going to solve a very famous Leetcode problem known as Rainwater trapping problem.

Solution with O(1) space can be found here: www.techiedelight.com/trapping-rain-water-within-given-set-bars
Assignment problems: www.techiedelight.com/Category/Array/

Follow for updates:
Instagram: www.instagram.com/Anuj.Kumar.Sharma
LinkedIn: www.linkedin.com/in/anuj-kumar-sharma-294533138/
Telegram: t.me/coding_enthusiasts


DSA-One course: www.youtube.com/watch

Link to the code: www.geeksforgeeks.org/majority-element/
Practice problems: www.interviewbit.com/courses/programming/topics/arrays/

Use #DSAOne to spread knowledge and show your support on LinkedIn, Instagram.

Join the Telegram Group for DSA-One course: t.me/dsa_one


Ignore these tags:

trapping rainwater problem
trapping rain water
trapping rain water problem
trapping rainwater problem leetcode
trapping rainwater
problem solving
trapping rain water leetcode
trapping rainwater leetcode
trapping rainwater leetcode java
trapping the rainwater problem
trapping rain
rain water trapping problem
leetcode trapping rain
rainwater trapping
trapping water problem
rain water problem
trapping rain water problem explanation
rainwater problem
trapping rainwater problem
trapping rain water
trapping rain water problem
problem solving
trapping rain water leetcode
trapping rainwater leetcode
trapping rainwater leetcode java
trapping rainwater problem leetcode
trapping the rainwater problem
trapping rainwater
leetcode trapping rain
trapping rain
rain water trapping problem
trapping rain water problem explanation
rain water problem
rainwater problem
trapping rainwater leetcode python
trapping rainwater problem
trapping rain water
trapping rain water problem
trapping rainwater problem leetcode
trapping rainwater leetcode
trapping rainwater leetcode java
trapping water problem
trapping rainwater
rain water trapping problem
trapping rain water problem explanation
trapping rain water leetcode
rain water trapping problem using stack
trapping rain water solution
rainwater trapping
problem solving
rain water problem
rainwater problem

trapping rain water problem
trapping rain water
rain water trapping problem
trapping rainwater problem
rainwater trapping problem
anuj bhaiya
trapping rainwater
tapping rain water problem
trapping rainwater leetcode
trapping rain water leetcode
rain trapping problem
42. trapping rain water
water trapping problem
container with most water leetcode
container with most water
dsa problem solving
trapping water problem
rain water problem
rain water tapping problem
dsa question
rain water trapped
leetcode 42
dsa
rain water trapping
tapping rainwater
dsa one
rain water
rainwater
anuj bhaiya java
largest rectangle in histogram
leetcode solutions
trapping rain water problem in c++
anuj bhaiya dsa
leetcode
rain water preservation code
rain water trapping problem using stack
rainwater preservation code in java
trap rain water problem
trapping rain water problem in java
trapping rain water problem pepcoding
pepcoding
rain water preservation java code
trapping rainwater problem pepcoding
11. container with most water
data structure
love babbar
rainwater preservation java program
rainwater preservation program in java
tapping rain water
tapping rainwater problem
trapping rain water pepcoding
water trapping
anuj bhaiya resume
array problems
arrays in java
dsa questions
java dsa
leetcode trapping rain water
minimum swaps required to bring all elements less than or equal to k together
rain water preservation code in java
rainwater harvesting
rainwater preservation in java
trapping rain water 2
trapping water leetcode
anuj
array dsa
best time to buy and sell stock ii
best time to buy and sell stock leetcode
buy and sell stocks leetcode
chocolate distribution problem
data structures
dsa array
dsa java
maximum profit by buying and selling a share at most twice
maximum water between two buildings
rainwater preservation java code
stock buy and sell leetcode
stock span problem
trapping rain water java
trapping rain water neetcode
trapping rain water python
trapping rainwater problem using stack
trapping water
two pointer problems
water collection
water connection problem gfg
water jug problem in artificial intelligence

Content

Hey, what's up guys, Anuj here and welcome to the DSAOne course., In, today's.

Video.

We are going to solve a very interesting problem, which is rainwater.

Trapping.

Problem.

This is very common problem.

It has been asked a lot, but it uses a very good concept, which is Array Preprocessing, we'll, see about preprocessing.

Actually.

We've already seen preprocessing in buy and sell stocks.

We thought of way which is preprocessing, and we would be doing the same type of thing.

Here.

Let's understand the problem a little bit in rainwater trapping problem.

You are given multiple buildings or blocks, whatever you would like to call them, their heights are given, say, it's height is 3.

This one's 1, here is height.

2.

This is 4, 0 height, in this way.

They are standing, suppose on earth, in a 2d plane, and you have to drop water from above it's raining and water is coming from above, okay.

So.

Some of the rainwater will get trapped here when the rain gets over., The water will get stored.

You have to tell how much water will be stored.

How much rainwater is getting trapped.

So.

Now you must understand the name of this problem.

See, water will be stored here in this area.

It won't be stored above this because will get out then.

It, won't store here.

The water will just get out.

From.

Water will be stored where it's possible.

This block also has space.

So the water is here too.

And from here, it will go out too.

There's, no water, here.

So.

The water is stored in the area where I've marked it with red.

So.

You have to tell how much water is stored here., You have to answer in blocks or units, like 1 2, 3.

So the water is stored up to 3 blocks here.

And how much is here.

1 2, 3 4 5.

So water is stored here up to 5.

Blocks., So 5+3 will be 8.

So.

Our total is 8, that is, 8 units of water will be trapped.

Here.

So.

You have to tell how these 8 will come.

So.

This is a unique type of problem, very interesting.

Problem.

Try to solve it.

I have given you a hint for preprocessing, that is going to be used here.

Means.

You have to preprocess this array, and you have to store it as an axiliary array., So I've, given you a big hint, now try to solve it.

And after that we'll, go ahead.

If.

You guys would have thought.

You must have wondered where the water is getting stored.

If.

We go to every index, and look at any index water will get stored in an index when its previous and its next block are higher than it.

Then.

Water can be stored.

Can water, be stored here? It cannot because there's no higher block before it.

There is one after it, but there's no block before it.

So in this index.

Water cannot be stored.

You can try it for everywhere, like why is water getting stored here.

Because before this? There is a building and to it's right? There is a building.

That's.

Why water is getting stored here., You can check anywhere, here, there's, no storage of water because there's no building to its left or right higher than it.

Is.

Why.

Here is no water storage.

There is a building higher to its left, but not to its right.

And.

The same is here.

There is no building to its right.

So.

You have understood one thing if we want to know where is the water getting stored, then all we have to see is there must be a building to its left to its whole left, which is bigger than it, and a building higher than it to its right.

So.

We understood that.

Now we have to know how much water is getting stored on every index.

What can be the formula for that.

Think about that.

Now.

We are getting into preprocessing.

How?.

What I'll do is check for every element, which is the building higher than it to its left.

So I will make an auxiliary array, or left.

Array.

Which will tell about which building has the maximum height to its left.

There's, no building before it.

So its height will be taken, 3.

So.

This will be 3.

Now before this.

We will see the maximum between these two.

So obviously between these 3 is bigger, so there's a building before this whose height is 3.

So here.

It will be 3.

Then, we'll, come here.

And between 2 and 3 3 is the higher one.

So there's a building with height 3 before it Now here, 4 is bigger between 4&3.

So 4 will be written here.

Than between 0 and 4, there's, a building before 0, which is 4., Between 1&4, 4 is still bigger.

And in the rest 2 and 3, 4 is the higher one.

So.

We've created a left array.

Similarly, we will make an array for right side too.

Because we want to check both of the sides, right.

Let's make an array for right side.

So for this array, I'll call, it right.

And.

We will start filling it from the right side.

Now.

We see, which is the bigger one to its right.

So this is the biggest.

So this will be 2.

Now between 2&3, which is bigger.

Its height is 3 and its the higher one.

So.

This will be 3.

Now here, between 1&3.

So obviously 3 is the bigger one.

There's, a building to its right side whose height is 3., Between, 0&3, who's, higher, 3.

So basically in every index, the value is telling us that to its right, because this array's name is right, which building has the highest height or is maximum.

Here, between 4&3, 4 is the bigger one in 2&4, 4 is the bigger one.

Then again, 4(x2).

So.

We have created two arrays, left and right.

These arrays are different from this array using O(n) space.

We have created these arrays.

So.

We have created this.

Now.

Our work is to go to every index, how much water can be trapped.

There? Now.

We will apply a formula here and that formula basically is, on any index, that is on any position.

We will check the maximum height to its left and right.

And the one, which is smaller of the two, will be the unit of water store able in them.

How? If.

You come here.

The maximum height to its left is 3 and to the right is 4.

Okay.

This is the 3 building.

And this one's 4 to its right.

Between them.

The one who's smaller will be how much water storable in that position, right.

So between 4&3, 3 is the smaller.

And it is the amount of water that can be stored., We can even see, if the water tried to hold 4 unit of water.

Then it would just spill out.

Smaller.

One between 4&3 is 3, which is the amount of water.

It is able to hold.

But there's also a building at the bottom.

So this much amount of water will not be stored.

So.

We have got the formula, which is the one, which is smaller between left and right, take that and subtract the height of the building on it.

This will tell us how much water can be stored on that index or block or unit.

So.

The formula is.

So formula for any index 'I', is Math.min(left(I),right(I)) - a(I) So for any index (I).

The formula is take the minimum from left and right and subtract the height of the building.

And that is the amount of water, stored able., Like here, start from this one, for this its 3&4.

The smaller is 3, subtract 3 from 3, you'll, get zero.

So no water is being held here.

Water.

Held is 0.

Here.

4&3, smaller.

One is 3, subtract the height from it, 3 - 1, which is 2.

So.

The water being held here is 2.

Here, between 3&4, smaller is 3, 3 - (height)2, which is 1.

So.

The water held here is 1.

Block.

Between.

4&4, smaller is 4, 4 - 4 = 0.

So here is zero.

Smaller of 4&3 is 3, 3 - 0, which is 3.

So 3 blocks of water is stored here.

Now.

Here.

4&3, smaller is 3, 3 - 1 which is 2.

So two blocks of water is stored here.

Let's.

See here, between 4&3, 3 is smaller, 3 - 3, which is 0.

Between.

4&2, 2 is smaller, 2 - 2, which is 0.

Now.

You will add these numbers, 2 + 3, which is 5, 5 + 1, which is 6, 6 + 2, which is 8.

So.

Now we know that 8 blocks of water is being stored here.

So, see, it's, very simple.

The code is going to be very easy.

Let me code this.

And then you will understand it better, it's going to a simple code.

You guys can see.

Two.

Auxiliary arrays are made here, left and right and we solve using those.

And this is the formula used.

So.

This is going to be a very simple code.

You guys can try it? Yourself.

Otherwise I.

Am doing it.

Okay, I have coded this.

Its got a bid code, actually, there, wasn't space below so I wrote, it there.

So, same logic that you guys saw, I've written the same logic.

First.

We get an array, which represents heights of the blocks.

This is 'n', length of the array, I've created two arrays.

One left and another one right.

We have initialized them with the same length.

Then left(0) will be a(0).

We have assumed the first position to be a(0)., And I've filled the left array in this way.

So left[I] will tell the index of any position of the left.

I - 1 means, the maximum from the current and previous element will come here.

Similarly.

We have filled the right array, right[n - 1] = a[n.

- 1], means the last position in right will be the same as the position of the element.

And.

We are going from the back to the start in array, from I=n - 2, until I becomes greater than or equal to 0.

So, right? I will basically be Math.max of right.

I + 1, which is just next element, and the maximum from the current element.

So, our left and right array have been filled.

And now we have created a variable 'ans' in which our final answer will be shown., And I've filled it using the formula I told you.

So, we are going from 0 to n, math.min of.

If we want to tell how muny blocks of water is on any index, for that, we have to get minimum of left(I) and right(I), and subtract a(I),the height, from it.

And.

The result of that will be added into answer and return that answer And.

We would be done here.

So.

This is a big code, but a simple one.

You can code this easily in 2, minutes., With this.

The problem is solved.

And most of our problems in array are solved.

After this.

We will go ahead with sorting in arrays.

So I hope you like this video, like this video, subscribe to the channel, and I'll see it in the next video.

FAQs

What is the hint for trapping rainwater? ›

The key idea to solve this problem is to understand that rainwater can only be trapped if there exists a block of greater height, both on the left and the right side than the current block. Then rainwater can be trapped on top of the block.

What are the problems with rainwater harvesting? ›

Rainwater harvesting systems require regular maintenance as they may get prone to rodents, mosquitoes, algae growth, insects and lizards. They can become breeding grounds for many animals if they are not properly maintained.

What is the brute force approach in trapping rainwater? ›

Approach 1 (Brute Approach): This approach is the brute approach. The idea is to: Traverse every array element and find the highest bars on the left and right sides. Take the smaller of two heights.

Do you need to filter rainwater? ›

Rainwater might not be safe for household use without additional treatment. Before using collected rainwater for drinking, bathing, or cooking, consider whether treatment is needed to make it safe. Testing the water can determine if there are harmful germs, chemicals, or toxins in it.

Do I need to filter rainwater for plants? ›

Filtration removes any leaves or other organic matter from the water, which is great for reducing the risk of disease carry-over and allowing you to use your harvested rainwater on your youngest plants, enabling truly sustainable gardening for all of your leafy friends.

Is rainwater collection worth it? ›

Absolutely. The time-tested benefits of rainwater harvesting can help you conserve groundwater, save the energy required for tap water, limit stormwater runoff, nourish plants, and keep money in your pocket.

Is rainwater harvesting easy? ›

Rainwater harvesting is a very simple method that can be practiced by anyone. There are primarily two types of rainwater harvesting methods. The first one is surface runoff harvesting. In this method, the water that runs off the surface is focused on.

What are the different types of rainwater harvesting? ›

There are three main types of rainwater harvesting system: direct pumped, indirect pumped, and indirect gravity.

What is the trapping method? ›

Trapping is a method of capturing wildlife by humans using devices specifically designed to restrain an animal in place without the need for continual human presence. Traps can be set and left, making them resource efficient from the standpoint of the trapper.

What is rain water harvesting explain the two techniques used? ›

Rainwater harvesting (RWH) is the collection and storage of rain, rather than allowing it to run off. Rainwater is collected from a roof-like surface and redirected to a tank, cistern, deep pit (well, shaft, or borehole), aquifer, or a reservoir with percolation, so that it seeps down and restores the ground water.

What is the easiest way to filter rainwater? ›

The best filtration options for making rainwater potable are reverse osmosis and distillation. Mechanical filtration (via a sediment filter or Rusco spin-down system) is also integral to the success of rainwater treatment. A rainwater collection system can catch most large particulate matter, such as leaves and twigs.

What is the best filtration system for rainwater? ›

All-In-One Filter: Reverse Osmosis System

Countertop reverse osmosis units are the best option for rainwater filtration. These systems are placed on your kitchen countertop and designed for treating water in batches. Simply add a batch of rainwater collected from your tank to the RO system, then switch the machine on.

What micron filter for rainwater? ›

NSF/ANSI Standard 42 refers to the removal of specific aesthetic or non- health-related contaminants (chlorine, taste, odour and particulates) Micro/Ultra filtration membrane filters (0.1 - 0.01 micron) can effectively treat water by removing sediment and bacteria.

How do I keep my rain barrel water from turning green? ›

Clean the barrel using a non-toxic substance such as vinegar to remove residue or algae. ✔ Clean out downspouts and roof gutters for the most effective mosquito control. However, if you find mosquitoes in your rain barrel, you may use dunks. A quarter dunk added monthly may be adequate for a 55-gallon rain barrel.

How long can you keep water in rain barrel? ›

Rainwater can be stored indefinitely if you have the right systems in place to ensure the water is safe for drinking once it leaves the tank and into your water system.

Should you treat water in a rain barrel? ›

In addition to cultural practices, researchers recommend chemical treatment of rain barrel water before irrigating a garden grown for consumption, to reduce the risk of exposure to harmful pathogens.

What is the best material to store rainwater? ›

One of the most economical choices for rainwater harvesting, polyethylene storage tanks are versatile and can be used above or below ground. Polyethylene storage tanks are available for potable and non-potable applications and come in a wide range of capacities, shapes, sizes and diameters.

Do you connect rain barrels at the top or bottom? ›

Attach a hose to the upper hose bib located near the top of the barrel, on one of the end barrels. The upper hose bib on the other barrels should remain capped. This outlet is for any overflow during a heavy rain event that fills the barrels. Direct the overflow hose into a permeable garden area.

Is rainwater no longer safe? ›

They found that levels of at least two forms of PFAS in rainwater, PFOA and PFOS, “often greatly exceed” the safe levels in drinking water, as the U.S. Environmental Protection Agency (EPA) advises.

How do you make simple rainwater harvesting? ›

Redirecting water with pipes: Rainwater will be redirected towards the container through PVC pipes. These PVC pipes or gutters come in cylindrical shapes and can be easily attached to the drain pipes on the roof to redirect the water towards the storage tank.

How to build a rain water collection system? ›

Tips for Installing a Rainwater Collection System
  1. Take roofing material into consideration. ...
  2. Choose a barrel designed for holding water. ...
  3. Locate barrel with safety in mind. ...
  4. Block up rain barrels several inches. ...
  5. Attach spigots and hose connections finger-tight only. ...
  6. Clean gutters periodically.
Mar 15, 2020

Which is the cheapest method of rainwater harvesting? ›

Rain Barrels

This is the easiest and cheapest method of rainwater harvesting, especially for homes. In this method, barrels or water tanks are installed below the downspouts of a rooftop guttering system. The water is then funneled or directed into the tanks.

What is indirect pumped rainwater harvesting? ›

Another method is the indirect pumped system which doesn't rely on gravity to supply water to the outlets. Harvested rainwater is instead pumped to a tank that can be installed at any level, with an additional booster pump used to keep the water pressurised.

What is rainwater harvesting class 3? ›

Rainwater harvesting: Rainwater harvesting is the process of collecting and storing rainwater that falls on roofs, parks, roads, and other open areas. This runoff water can be stored or recharged into the groundwater system.

How do you collect rainwater in the wild? ›

There are two primary methods of collecting rainwater. The first is to use any and all containers you might have on you. The second is to tie the corners of a poncho or tarp around trees a few feet off the ground, place a small rock in the center to create a depression, and let the water collect.

How do you maximize rainwater harvesting? ›

To increase your ability to store rainwater you could stack barrels, or use multiple slimline barrels that sit snugly in corners or against walls. Or go large – very large – by repurposing an IBC tank. IBCs usually come in at around 250 gallons (1000 liters).

Where is the simplest way to deal with rain water direct it to? ›

Rain barrel – Easy solution for every house

This is the simplest method of rainwater harvesting. A downspout attached to the rooftop directs the rainwater from the roof into a barrel-shaped structure where it can be stored for the household use.

How do I redirect water runoff from my driveway? ›

How to Divert Water Runoff from Driveway. Dig a trench. Use a shallow, gravel-filled trench to catch and slow runoff, especially at the base of a slope or alongside a driveway or patio. For slopes, consider creating a dry creek to catch, slow down and direct runoff, perhaps to a rain garden (see below).

How do you slow down water runoff? ›

What can you do to reduce the runoff from your property?
  1. Disconnect/Redirect Downspouts.
  2. Use a rain barrel to capture rain from your roof.
  3. Plant a rain garden.
  4. Plant trees.
  5. Reduce impervious surfaces; install permeable pavement.
  6. Plant a green roof.
May 2, 2023

How do you collect rainwater without mosquitoes? ›

Use a rain barrel with a mosquito-proof screen (fine mesh–1/16th of an inch) under the lid and covering the overflow hole. Keep your rain barrel lid and all connectors in the system sealed. Place your barrel on a surface that will soak up or promptly drain water that has overflowed.

What are 10 sources of water? ›

Freshwater sources include rivers, lagoons, lakes, wetlands, icebergs, glaciers, groundwater, groundwater currents, aquifers, ice caps, and ice fields.

How do you slope rainwater away from your house? ›

Digging a swale is an ideal way to direct excess water when it is causing erosion on a hill or slope. A swale should slope downhill, and the trench should gradually get deeper. If your landscape allows, the swale should deepen by 1 inch for every 10 feet. It should also be two to three times as wide as it is deep.

How do you collect rainwater without a barrel? ›

Any clean container can be used to collect rain from rooftops, such as buckets, pans, even garbage cans. During the next rain, look at your roof for points of heaviest rainfall run off. You can gather your containers into one area or spread them out in each area that has run off.

How do you control water from gutters? ›

12 Solutions for Better Gutter Drainage
  1. Install Gutter Guards. ...
  2. Regular Maintenance and Gutter Cleaning. ...
  3. Install Downspout Extensions. ...
  4. Use Splash Blocks at the End of Downspouts. ...
  5. Install Buried Corrugated Drainage Pipes. ...
  6. Improve Yard Grading and Slope. ...
  7. Consider Installing French Drains. ...
  8. Direct Runoff Toward Storm Drain/Dry Well.
Aug 4, 2022

What is the easiest method of rainwater harvesting? ›

Rain Barrels

This is the easiest and cheapest method of rainwater harvesting, especially for homes. In this method, barrels or water tanks are installed below the downspouts of a rooftop guttering system. The water is then funneled or directed into the tanks.

Where is rainwater harvesting most needed? ›

Harvesting rainwater for use in your household may be essential for rural areas, and can reduce your water bills in urban areas. The best water savings are achieved by using rainwater indoors, for example to supply toilets and washing machines, in addition to garden watering.

Top Articles
Latest Posts
Article information

Author: Nicola Considine CPA

Last Updated: 20/09/2023

Views: 5243

Rating: 4.9 / 5 (49 voted)

Reviews: 88% of readers found this page helpful

Author information

Name: Nicola Considine CPA

Birthday: 1993-02-26

Address: 3809 Clinton Inlet, East Aleisha, UT 46318-2392

Phone: +2681424145499

Job: Government Technician

Hobby: Calligraphy, Lego building, Worldbuilding, Shooting, Bird watching, Shopping, Cooking

Introduction: My name is Nicola Considine CPA, I am a determined, witty, powerful, brainy, open, smiling, proud person who loves writing and wants to share my knowledge and understanding with you.