# Container With Most Water > Choose two vertical lines that hold the most water. Start with the widest pair and always move the shorter line inward, which turns an O(n²) search into one pass. - Track: DSA (Sliding Window) - Level: Medium - Format: Step-through player - Author: Aayush Ostwal - Published: 25 October 2026 · Updated: 27 October 2026 - Topics: Two pointers, Greedy - LeetCode: https://leetcode.com/problems/container-with-most-water/ - Canonical URL: https://compoundengineer.com/library/dsa/container-with-most-water Two pointers · Opposite ends Medium · O(n) time · O(1) space ## Problem You are given an integer array height of length n. Line i is a vertical line from (i, 0) up to (i, height[i]) . Pick two lines. With the x-axis they form a container, and the container can't be tilted. Return the most water a container can hold. Example 1 Input: height = [1, 8, 6, 2, 5, 4, 8, 3, 7] Output: 49 (lines 1 and 8: min(8, 7) × 7) Example 2 Input: height = [1, 1] Output: 1 Constraints 2 ≤ n ≤ 10^5 0 ≤ height[i] ≤ 10^4 ### What the problem asks for - Choose exactly two lines, at positions i So one pair holds min(height[i], height[j]) × (j − i) . Wide pairs help, and tall pairs help, but they pull against each other. ## Start with the direct approach Measure every pair with that formula and keep the largest. ### The code ### Time and space Time: O(n²). There are n × (n − 1) / 2 pairs, which is about 5 × 10⁹ for n = 10⁵. Space: O(1). ## Building the faster solution All the time goes into measuring pairs. So the question is: which pairs can we skip without measuring them? ### Start with the widest pair The first and the last line form the widest pair, and every other pair is narrower. So another pair can only win by being taller . But a pair's height is capped by its shorter line, and that is the line to watch. ### The shorter line can be dropped Measure the pair, and call its shorter line lo and the other hi . Any other pair that uses lo has its partner closer than hi . That pair is narrower, and its height is still capped by lo . So it cannot hold more than the pair we just measured. That means lo is finished. We measure the pair, drop the shorter line and move that pointer inward. On the example, the pair (0, 6) has heights 3 and 4, so line 0 is dropped. ### Why not drop the taller line? The shorter line would stay in the pair and still cap the height, while the pair gets narrower. We lose width for nothing, and we might throw away the best pair. Equal lines are safe either way, because the argument holds for both. ## The solution - Put lo on the first line and hi on the last. Set best = 0. - Measure min(height[lo], height[hi]) × (hi − lo) and keep the larger of it and best. - height[lo] ≤ height[hi]⟶lo moves right - otherwise⟶hi moves left - When the pointers meet, return best. Pick an input and press Play , or use the arrow keys. ### Equal lines and other edge cases When the two lines are equal, the code drops lo , which is safe. With [1, 1] there is one pair and the answer is 1. On [4, 3, 2, 1, 4] the very first pair is the best, 4 × 4 = 16, and the rest are only checked. ## Why it works - We never skip the best pair. Each time a line is dropped, every pair we give up that includes it is narrower and capped by the same line, so it cannot beat the pair we just measured. - Every pair is covered. A pair is either measured, or it contains a dropped line. The pointers only stop when they meet, so no pair is left unaccounted for. - The loop ends. Each pass moves one pointer one step closer, so it stops after n − 1 passes. ## Complexity O(n) Time. Here's why: the pointers start n − 1 apart and every pass moves one of them one step closer. That is at most n − 1 passes, each doing a fixed amount of work. O(1) Space. Two pointers and best . Nothing grows with the input. ## What can be optimized - The big-O is already optimal. Any line can be part of the best pair, so every line must be read, and O(1) space is the least possible. - A small speed-up: after dropping a line, keep skipping lines that are not taller than it. A narrower pair with a line that is not taller cannot win, so we save those measurements. The worst case is still O(n). ## Check your understanding Checkpoint 1 · Predict: on [3, 9, 2, 5, 8, 8, 4] we just measured (1, 5) , heights 9 and 8. Which pointer moves, and where to? Answer hi moves, from 5 to 4. The right line (8) is the lower one, so it is dropped. Checkpoint 2 · Why not move both pointers inward every time? Answer The taller line may be part of the best pair. At (1, 6) moving both goes to (2, 5) , which skips (1, 5) , the pair with 32. Checkpoint 3 · For [4, 3, 2, 1, 4] , what is the answer and how many pairs does the code measure? Answer 16 , from the first pair (0, 4) . It measures 4 pairs: 16, 9, 4 and 1. That is n − 1, not all 10 pairs. ## Interviewer follow-ups Open one to see an answer you could say out loud. "Convince me you never skip the best pair." What they are checking Whether you can prove the greedy step, or only repeat "move the shorter one". A strong answer Each time I drop a line, every pair I give up that includes it is narrower and capped by that same shorter line, so it cannot beat the pair I just measured. I only skip pairs that cannot win, and the pointers stop only when they meet. "Now the lines hold water between all of them, not just between two. How much water in total?" What they are checking Whether you can adapt the two-pointer idea. This is Trapping Rain Water. A strong answer The water above a position fills up to the lower of the tallest line on its left and the tallest on its right, minus its own height. Keep two pointers and the tallest line seen from each side, and always move the pointer whose side has the lower tallest line, because that side already decides its level. O(n) time, O(1) space. "Heights go up to 10,000 and there can be 100,000 lines. Can the area overflow?" What they are checking Whether you check the largest value before you trust the code. A strong answer The biggest area is 10,000 × 99,999, about 10 9 . A 32-bit integer holds about 2.1 × 10 9 , so it fits, with little room. If the limits grew I would use a 64-bit number. In Python it does not matter. ## Spot this pattern - The answer depends on a pair of positions, and trying all pairs is O(n²). - The value of a pair is limited by one of its two ends (a min). - Moving one end inward lets you discard it for good. When it does not apply: if a pair's value is not capped by one of its ends (for example height[i] + height[j] ), dropping an end proves nothing, and this argument fails. ## Solution code ### Python ```python class Solution: def maxArea(self, height): lo, hi = 0, len(height) - 1 # start with the widest pair best = 0 while lo < hi: water = min(height[lo], height[hi]) * (hi - lo) best = max(best, water) # the lower line caps every container it can still form, so drop it if height[lo] <= height[hi]: lo += 1 else: hi -= 1 return best ``` ### Java ```java class Solution { public int maxArea(int[] height) { int lo = 0, hi = height.length - 1; // widest pair first int best = 0; while (lo < hi) { int water = Math.min(height[lo], height[hi]) * (hi - lo); best = Math.max(best, water); // the lower line caps every container it can still form, so drop it if (height[lo] <= height[hi]) { lo++; } else { hi--; } } return best; } } ``` ### C++ ```cpp class Solution { public: int maxArea(vector& height) { int lo = 0, hi = height.size() - 1; // widest pair first int best = 0; while (lo < hi) { int water = min(height[lo], height[hi]) * (hi - lo); best = max(best, water); // the lower line caps every container it can still form, so drop it if (height[lo] <= height[hi]) { lo++; } else { hi--; } } return best; } }; ``` --- From Compound Engineer (https://compoundengineer.com), visual lessons for engineers. The page above is the full interactive version.