3 ms·
I am not a mathematician, but the problem seems easier to intuit. Like a lot of math problems, a formal proof is annoying but I definitely think a regular joe c
by Gunax 7y ago
I am not a mathematician, but the problem seems easier to intuit. Like a lot of math problems, a formal proof is annoying but I definitely think a regular joe can convince himself why this works.
Start at i,j with heights h_i < h_j. Then we know that if i is involved in the solution, it must be paired with j.
We know this because if it's paired with any other point, the other point is either:
a. shorter than h_i, which means it's shorter than h_j. And since it's also closer to i than j is, the area is smaller.
b. equal or taller than h_i. But this will never make a larger area since the height will be limited by h_i, but the distance smaller than the distance from i to j.
So we can stop considering i as part of the solution space.
Of course that doesnt make it a good interview question. It relies on a brilliant stroke of insight, rather than relying on established data structures or algorithms.
- ninjinxo 7y agoI think it's much more clear if you start by trying to apply the constraint to the brute force algorithm. The water container area is the distance the two sides are apart (width), by the height of the shorter side [therefore, the longer side acts to mimic it]. Doing brute force on array $[n_1 n_2 ... n_k]$; You'd naturally start at $n_1$ and calculate volume $V(n_1, n_k)$ and work your way inwards calculating each volume. However, if at any point $n_1$ is the shorter side, then the secondary side $n_j$ now mimics $n_1$ in height; and therefore, any new side closer to $n_1$ cannot increase the height of the container (but would decrease the width, and therefore area). Then you'd continue the same with $n_2$, breaking iteration when $n_2$ becomes the shorter side or if $n_2$ cannot develop a greater area than $n_1$ did (either n_1 > n_2 or oldArea > n_2 * width). etc.
- dmurray 7y agoAs a sometime mathematician, I'd say that's a perfectly complete and formal proof.