Max water trapped between elements of array - how to prove global optimality?

16 Views Asked by At

Going through the solution to the question here. The question gives us an array representing heights of blocks and asks which two blocks can store the most water (in terms of area) between them. The solution involves maintaining two pointers, one at the beginning of the array and one at the end. At each step, a decision is to be made. Should we increase the left pointer or decrease the right one. The argument in the solution is to move the pointer with the lower array value. The argument is that moving the pointer with the higher array value can't possibly increase the area while moving the other one might increase it. But, this still seems like a greedy strategy. Is it possible to mathematically prove that the solution will be globally optimal?