Spent 8 hours on a single problem, still not convinced.
So I am quite a mathematician and I like proving things.
Problem: Container with most water.
https://leetcode.com/problems/container-with-most-water/description/
What I have tried:
Brute approach done. Optimal approach - done but UNABLE to visualize, even from the hello-interview website.
Proof I made for that optimal solution that somehow works it out, but doesn't convince me:
Aim: To maximize f(x,y) = (y-x) * min (ax, ay), where let x and y be left and right indices (x < y). Let array be 1-indexed from a1, a2, ... an.
for some x < k < y.
Also remember the result that min (a, b) <= a and min (a, b) <= b. Its handy in this proof.
Case-1: If ax < ay.
In this case, then using basic inequalities we can work out that f(x, k) < f(x, y)
So areas formed using (x, x+1), (x, x+2), ..., (x, y-1) are all less than the area found using just (x,y). So they can be rejected for analysis.
Similarly for case-2: if ax > ay, we can show that f(k, y) < f(x, y). Thus prune more unwanted search space.
Case-3: ax = ay. In this, we can just change any one of them or even both doesn't matter. Just change them.
Then I also dry run it on set of inputs a lot of times.
Here:
and had a few more images but can not add.
After this also I was not convinced. So I try to generate the matrix itself. Example for the image above the symmetric matrix with diagonal entries zeros would be:
0 4 8 12 16 20 24 28 32 36 40 44
4 0 6 12 18 24 30 36 42 48 54 50
8 6 0 8 16 24 32 40 48 56 56 45
12 12 8 0 10 20 30 40 50 54 49 40
16 18 16 10 0 12 24 36 48 45 42 35
20 24 24 20 12 0 15 28 *270 36 35 30
24 30 32 30 24 15 0 14 30 27 28 25
28 36 40 40 36 28 14 0 14 18 21 20
32 42 48 50 48 270 30 14 0 9 14 15
36 48 56 54 45 36 27 18 9 0 7 10
40 54 56 49 42 35 28 21 14 7 0 5
44 50 45 40 35 30 25 20 15 10 5 0
with 270 being maximum.
If you look at it we start from the upper rightmost element of this matrix in most two-pointer problems. As it denotes l = 0 and r = n-1.
Now we have two options either go down the matrix or go left of matrix. Both ways, the width decrease by 1.
But the height VARIES and has no such pattern. There's just no way to tell anything.
So any normal person would go in the direction where height increases.
But what if the height DOES NOT increase. In that case - we are STUCK.
So we decide to remove away the element that controls heights - the lesser of the two - just for exploration.
Then WHY this so random exploration leads to the solution. Why it doesn't skip any other potential solution. That is what I wish to understand.
Using matrix helped me visualize two-sum and prove it intuitively. But in that problem, the array was sorted. But here it is not.
So I realized I AM AT MY LIMIT quite literally.
My not-so-optimal code O(N):
(the else block I put there was because I was getting stuck whenever hh <= h into an infinite loop.)
#include <iostream>
using namespace std;
int main (void)
{
int n = 0; cin >> n;
int a\[n\] = {0}; for (int i = 0; i < n; ++i) { cin >> a\[i\];}
int l = 0;
int r = n-1;
int max\_area = 0;
while(l < r)
{
int w = r-l;
int h = min (a\[l\], a\[r\]);
int area = w\*h;
if (max\_area < area)
{
max\_area = area;
}
int h1 = min(a\[l+1\], a\[r\]);
int h2 = min(a\[l\], a\[r-1\]);
/\*
respective areas
a1 = h1(w-1) and a2 = h2(w-1).
This means a1 and a2 are proportional to the new heights h1 and h2.
So just pick whichever height is greater than old height h.
That leads to the greater area.
BUT else case, if out height is already more - why would we want to move??
as h\_old > hh, this means that any new area you calculate = hh \* (w-1).
Its guaranteed to be strictly less than the oldarea = h\_old \* w.
THIS causes an infinite loop if not handled carefully.
\*/
int hh = max(h1, h2);
if(hh > h)
{
if(hh == h1)
{
++l;
} else
{
--r;
}
}
else
{
if(a\[l\] < a\[r\])
{
++l;
}
else if(a\[l\] > a\[r\])
{
--r;
}
else /\*they are equal\*/
{
// change any one of them OR change both. doesn't matter.
++l;
}
}
}
cout << max\_area << endl;
return 0;
}