## 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**

- Take roofing material into consideration. ...
- Choose a barrel designed for holding water. ...
- Locate barrel with safety in mind. ...
- Block up rain barrels several inches. ...
- Attach spigots and hose connections finger-tight only. ...
- Clean gutters periodically.

**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?**

- Disconnect/Redirect Downspouts.
- Use a rain barrel to capture rain from your roof.
- Plant a rain garden.
- Plant trees.
- Reduce impervious surfaces; install permeable pavement.
- Plant a green roof.

**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**

- Install Gutter Guards. ...
- Regular Maintenance and Gutter Cleaning. ...
- Install Downspout Extensions. ...
- Use Splash Blocks at the End of Downspouts. ...
- Install Buried Corrugated Drainage Pipes. ...
- Improve Yard Grading and Slope. ...
- Consider Installing French Drains. ...
- Direct Runoff Toward Storm Drain/Dry Well.

**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.