@StefanPochmann

One word: Sublime. Your code also reminds me of how stupid I am. I would probably never be able to come up with this kind of solution if I was locked in a room for 2 months with this problem.

@BatCoder

I have spent a lot of time understanding this solution. I would try to summarise my thoughts here:

Consider this example: [3, X, 5], and we are working after the first iteration. That means l = 1 and r = 2

What is the information that we need to figure out the amount of water that can be on X? We need only two things:

Maximum water that can be on X
Value of X

Maximum water is not dependent on the value of X. It has to be obtained from the previous step. In this case, that has to be 3. Notice that the minimum of height[l] and height [r] of the previous step is also 3. This information is tracked by level. And X can only hold water if level is greater than X.

There can be three cases of X.

X > level and X < 5: then X cannot hold any water, but we need to update level.

For X = 4:

lower = 4.

level = max(4, 3) = 4

water += (4 - 4) += 0

X < level, then X can hold water, and we don't have to update level since for the next step maximum water will still be level units.

For X = 1:

lower = 1,

level = max(1, 3) = 3

water += (3 -1) += 2

X > 5 > level: In this case lower will change to 5. And level also needs to change. since, if there were more bins between 5 and X, then from this steps point of view, maximum water permissible water will be 5 units.

For X = 8:

lower = 5

level = max(5, 3) = 5

water += (5 - 5) = 0

Hope this helps.