LC 42. Trapping Rain Water (Hard)

🔗: https://leetcode.com/problems/trapping-rain-water/

Problem Statement

Given an integer array A of non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

Example 1:

Input:

[1,2,1,2,1]

Output:

1

Example 2:

Input:

[1,5,3,5,2,1]

Output:

2

This was the question I did in my second half of the day

Ngl, when I saw the Hard tag, I already knew this question was going to eat up a good amount of my time 😭

Usually for hard questions, I try thinking on my own first, but after a certain point I don't like spending 2-3 hours staring at the same screen. I would rather understand the thought process and move forward than stay stuck forever.

So for this one too, I first tried understanding the question on my own and later used ChatGPT as a mentor to help me think through the observations and understand the code. Hard questions are honestly exhausting (alwaysss).

The funny thing is that I wasn't even struggling with the solution initially. Why? BECAUSE I was struggling to understand the question itself 😀.

Like genuinely I was staring at the examples and wondering:

How is the water even getting trapped here?

Let's take:

[1,2,1,2,1]

If we draw it like walls:

    █    █ 
    █ █ █
------------
 1  2  1  2  1

Now imagine rain starts falling.

The question is asking:

How much water will remain trapped after the rain?

Not where the water falls.

Not where it flows.

Just the total amount of water stored.

The first thing I noticed was that water needs boundaries.

For example:

[3,1,3]

can store water.

But:

[3,1]

cannot.

Why?

Because there is no wall on the right side.

Similarly:

[1,3]

cannot store water because there is no wall on the left side.

So my first observation was:

Water needs a boundary on both sides.

Then another very random question came to my mind 😭.

I asked:

Can adjacent walls store water?

For example:

[3,3]

There are two walls.

Shouldn't they trap water?

But then I realized there is literally no space between them.

Water needs somewhere to sit.

There needs to be at least one index between the walls.

Something like:

[3,0,3]

can trap water because the middle position acts like a dip.

This was when I realized that we are actually storing water at indexes, not between walls.

Then I looked at:

[1,2,3,4]

and got confused again (wow Simran)

Why is the answer 0?

There are walls right?

But after drawing it, I realized there is no dip.

The heights keep increasing.

Water needs a lower position between boundaries.

A slope cannot trap water because everything simply flows away.

Then I got stuck on another thing.

Suppose:

[3,1,5]

At first I thought:

Do both walls need to be the same height?

Turns out they don't.

The walls can have completely different heights.

The only thing that matters is that there is a wall on both sides.

Then another stupid question popped into my head (my bad ehe)

For:

[3,1,5]

I was thinking:

|5 - 3| = 2

and wondering if somehow the answer depends on the difference between the walls.

But that logic immediately breaks.

The water is not dependent on the difference between the walls.

The important thing is:

If water rises above the shorter wall, it overflows.

So even though the right wall is height 5, the water level can only rise till:

3

because the left wall is shorter.

This was probably the biggest observation of the entire problem.

The shorter wall decides the maximum water level.

Then I started looking at individual indexes instead of the whole dip.

For example:

[4,2,0,3,2,5]

At:

index = 2
height = 0

The tallest wall on the left is:

4

The tallest wall on the right is:

5

The smaller wall is:

4

So water can rise till:

4

Current height is:

0

Therefore:

Water Stored = 4

And then suddenly it clicked.

I wasn't trying to find one giant container.

I was finding water stored at every individual index.

Then another thing confused me 😭.

The code had:

water += something

and I kept asking:

Why are we adding water?

Then I realized the question is asking for:

Total Water Stored

not

Water Stored at One Index

For example:

Index 1 -> 2 units
Index 2 -> 4 units
Index 3 -> 1 unit
Index 4 -> 2 units

The answer is:

2 + 4 + 1 + 2

which is why we keep doing:

water += currentWater;

instead of simply assigning a value.

Initially my mind directly jumped towards a two-pointer solution.

I wasn't really interested in spending too much time on the brute force because I could already feel there was some boundary-based observation hiding in the problem.

The biggest thing that helped me understand the optimal solution was:

If the left side is the smaller boundary, then the left side becomes the limiting factor and if the right side is the smaller boundary, then the right side becomes the limiting factor.

That eventually leads to the two-pointer solution and also in the beginning I need to find the solution within two boundaries so it strike me

The important things I noticed were:

1. Water needs boundaries on both sides.

2. There must be at least one index between the walls.

3. Water is stored at indexes, not at walls.

4. The shorter boundary decides the water level.

5. If water rises above the shorter boundary, it overflows.

6. Water is calculated for every index separately.

7. The final answer is the sum of water stored at all valid positions.

8. The optimal solution uses two pointers and processes the side that is currently limiting the water level.

This is the code that I wrote:

public class Solution {
    public long trap(int[] h) {
       //You can code here
       int n = h.length;
       int l = 0;
       int r = n-1;
       int leftMax = 0;
       int rightMax =0;
       long waterTrap = 0;

       while(l<r){
        if(h[l]<h[r]){
          if(h[l]>=leftMax){
            leftMax= h[l];
          }
          else{
            waterTrap += leftMax - h[l];
          }
          l++;
        }
        else{
          if(h[r]>=rightMax){
            rightMax= h[r];
          }
          else{
            waterTrap += rightMax - h[r];
          }
          r--;
        }
       }
       return waterTrap;
    }
}

My biggest learning from this question was that understanding the physics of the problem is way more important than memorizing the code.

Once I understood why water overflows from the smaller wall, the two-pointer intuition started making much more sense. Also, hard questions are exhausting (sorry for ranting so much but they are exhaustinggg!)

I genuinely don't mind taking help from AI after trying on my own. For me the goal is to understand the observation and intuition behind the solution, not pretend that I discovered everything instantly.

Another DSA log added hehehe.

I am tired noww! I need to start backend too ahhhhh and also improve my routine :))

Will definitely try to continue documenting more problems as I learn.

Any suggestions, corrections, or feedback would be appreciated.

Thanks for reading!!