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
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
|
while_loop_not_for_loop (I was thinking about a for loop, not a while loop), 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)
|
parents
|
intuition
|
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
|