leetcode/container_with_most_water

container_with_most_water

dz / leetcode / container_with_most_water

Summary

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]). Find two lines that together with the x-axis form a container, such that the container contains the most water. Return the maximum amount of water a container can store.

Node Tree

Nodes

URL
content URL
hyperlink https://leetcode.com/problems/container-with-most-water/

intuition
content This one took a moment for me to understand. The input array is a set of heights. A rectangular area is formed by taking any two heights, and multiplying the smallest height by the distance between eachother. The largest one maximizes the distance and the heights.
children intuition_post_hints, intuition_brute_force, intuition_brute_force_v2

intuition_brute_force
content Brute force solution involves finding the area of every combination, and keeping track of the maximum area.
children intuition_brute_force_v2 (iteration)
parents intuition

intuition_brute_force_v2
content For any two heights, the smallest is chosen, which means you can skip some computations. For example, only comparing a given height with heights greater than itself. This cuts the pairs in half.
parents intuition_brute_force, intuition

does_sorting_help
content If the list was sorted, would this help with performance? The largest height could be tested with all the other heights (n - 1). The second largest with the other heights (n - 2), (n - 1) + (n - 2) + (n - 3) ... There's probably some equation for this, but I think it's more efficient.

intuition_post_hints
content Hints about moving left and right. It's not quite divide and conquer, but I think I remember an algorithm talking about this. Start at the maximum distance (start/end of array), and move inwards towards the center. At each step, you move the one that points towards the lower line. I think it can be proved that this works without missing any big heights.
children proof_harder_than_implementation (even though I was mostly correct, I didn't understand why I was correct), two_pointer (Turns out I was on the right track), while_loop_not_for_loop (I was thinking about a for loop, not a while loop)
parents intuition

editorial
content LeetCode Editorial
children proof (elaboration on solution discussed here), two_pointer

proof
content Post I found with the solution (two-pointer) and the proof.
children proof_by_elimination, proof_harder_than_implementation
parents editorial
hyperlink https://leimao.github.io/blog/Proof-Container-With-Most-Water-Problem/

two_pointer
content They call this the "two-pointer" solution, and it's pretty much what I thought up after looking at the hints.
children while_loop_not_for_loop
parents intuition_post_hints, editorial

while_loop_not_for_loop
content The thing I didn't quite get right with my intuition was that it would be something that moves towards the center, so you'd use a for-loop that would go N/2 steps. Of course, if I had actually worked it out, it would clearly not behave like that. Instead, it's a while loop that's runs as long as the left is smaller than the right. It converges in O(N) time, single pass.
parents intuition_post_hints, two_pointer

proof_by_elimination
content The proof described here is succintly described as "proof by elimination". It goes through the two pointer problem, and shows how each iteration uniquely eliminates a certain number of candidates.
parents proof

proof_harder_than_implementation
content I agree with the conclusion presented here, which is essentially that you can come up with a solution pretty quickly that passes the tests, but not know formally why or how it works.
parents intuition_post_hints, proof