Container With Most Water is the 11th problem from Leetcode: Container With Most Water.
The question is asking: given a two dimensional coordinate system and a number of vertical lines, shown as a, b, c, d in fig.1. Finds the max rectangle such that it consists of any two of the vertical lines (short one is the rectangle’s height) and their distance on x-axis is width, for example, A and B, shown in Fig.1.
It’s straightforward to come out a O(n^2) algorithm due to the two-dimensionality, which naturally goes through width and height and compute the max one. However, the difficulty is to reduce the complexity to O(n).
Inspired by Simple-and-clear-proofexplanation, to reduce the complexity:
- First picks the leftmost and rightmost vertical lines, and they form a based rectangle, shown as A in fig.2. The reason is, as mentioned in 1, A is the most width rectangle, all other rectangles’ width can only be narrower, which triggers a key property explained in next.
Next step, it needs to scan other vertical lines one by one to find the max one. It either picks the leftmost line’s right neighbor, or rightmost line’s left neighbor. Here comes the critical part: how to know which one to pick? If try both, next step it also needs to try both, then soon the algorithm becomes exponential.
The key observation is, as mentioned in 1: always discard the shorter vertical lines, and try its neighbor. The reason is:
since the base rectangle is the widest, then from both sides to intermediate, the width becomes shorter. To find a larger rectangle, it must be the case that it needs to find a higher line.Therefore, it always discard the shorter one, shown in Fig.3, it grantees the algorithm is linear and find the max area.