Problem Link-link text
Please explain what is the correct & easy approach?
1 Like
The question involves some basic idea that I have mentioned below:
1. Minimum amount of water required to be held needs at least height to be 1. So start from 0 to n find the 1st index where height is atleast 1.
2. Iterate from this index to (n-1) and find out maximum height upto which it can hold water. Suppose at beginning height was 10 and the max obtained in range from begin to n - 1 was 20. So max capacity from begin to end = 10 (Max(begin, max_end)) for each column(suppose if height of others in range were 0).
3. Now when you know maximum storage possible for each block add to total amount. Put next begin index to location where max was found.
You can view my solution in Java here. Code Link
Hope it helps.
1 Like
Is there a practice version of this problem?
Either way my code for it : #include<bits/stdc++.h>#define fast ios_base::sync_with_stdio(0); cin.tie(0); - Pastebin.com
I have added comments in the code explaining how we solve it.
Did you check geeksforgeeks for this? I think it wa sunder “Trapping Rainwater”, although the solution seemed tricky to me 
1 Like