Container With Most Water - Leetcode Solution

Problem Link

💡 Step-by-Step Thought Process

Understand the problem: Find two lines that form a container with the maximum water area, given an array of heights.
Initialize left pointer to 0 and right pointer to the array length minus 1.
Initialize max_area to 0 to track the maximum area found.
While left is less than right, calculate the width as right minus left.
Calculate the height as the minimum of height[left] and height[right].
Compute the area as width times height and update max_area if the computed area is larger.
If height[left] is less than height[right], increment left; otherwise, decrement right.
Return max_area after the loop.

Code Solution

class Solution:
    def maxArea(self, height: List[int]) -> int:
        n = len(height)
        l = 0
        r = n - 1
        max_area = 0

        while l < r:
            w = r - l
            h = min(height[l], height[r])
            a = w * h
            max_area = max(max_area, a)
            
            if height[l] < height[r]:
                l += 1
            else:
                r -= 1

        return max_area

# Time Complexity: O(n)
# Space Complexity: O(1)

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int maxArea(vector<int>& height) {
        int n = height.size();
        int l = 0;
        int r = n - 1;
        int maxArea = 0;

        while (l < r) {
            int w = r - l;
            int h = min(height[l], height[r]);
            int a = w * h;
            maxArea = max(maxArea, a);

            if (height[l] < height[r]) {
                l++;
            } else {
                r--;
            }
        }

        return maxArea;
    }
};

public class Solution {
    public int maxArea(int[] height) {
        int n = height.length;
        int l = 0;
        int r = n - 1;
        int maxArea = 0;

        while (l < r) {
            int w = r - l;
            int h = Math.min(height[l], height[r]);
            int a = w * h;
            maxArea = Math.max(maxArea, a);

            if (height[l] < height[r]) {
                l++;
            } else {
                r--;
            }
        }

        return maxArea;
    }
}

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    let l = 0;
    let r = height.length - 1;
    let maxArea = 0;

    while (l < r) {
        const w = r - l;
        const h = Math.min(height[l], height[r]);
        const a = w * h;
        maxArea = Math.max(maxArea, a);

        if (height[l] < height[r]) {
            l++;
        } else {
            r--;
        }
    }

    return maxArea;
};

Detailed Explanation

Understanding the Problem: Container With Most Water

The “Container With Most Water” problem involves an array of non-negative integers, where each value represents the height of a vertical line drawn on the x-axis. The task is to find the two lines that, together with the x-axis, form a container that holds the most water. You are to return the maximum area of water that such a container can contain.

Example:

Input: [1,8,6,2,5,4,8,3,7]
Output: 49

The lines at indices 1 and 8 form the container with area = min(8,7) × (8−1) = 7 × 7 = 49.

Why This Problem Matters

This problem is a classic in the use of the two-pointer technique and is frequently asked in coding interviews. It teaches how to maximize values under constraints, how to analyze trade-offs between width and height, and how to approach optimization without checking every possibility.

Brute Force Idea (Inefficient)

The naive approach would involve checking the area formed by every possible pair of lines. This means two nested loops and a time complexity of O(n²), which is inefficient for large inputs.

Optimal Solution: Two-Pointer Technique

Since the area is determined by the shorter of two lines and the distance between them, we can use two pointers to efficiently find the maximum area. This method starts with the widest possible container (the outermost two lines) and moves inward to find better options.

Steps:

Initialize two pointers:
- left = 0 (start of array)
- right = height.length - 1 (end of array)
Initialize max_area = 0.
While left < right:
- Calculate width = right - left.
- Compute min_height = min(height[left], height[right]).
- Calculate area: area = width × min_height.
- Update max_area if area is larger.
- Move the pointer pointing to the shorter line inward:
  - If height[left] < height[right], increment left.
  - Else, decrement right.
Return max_area.

Example Walkthrough

Input: [1,8,6,2,5,4,8,3,7]

Start with left = 0 and right = 8 → height[0] = 1, height[8] = 7
Area = min(1,7) × (8−0) = 1 × 8 = 8
Since height[0] is shorter, move left pointer → now left = 1
Now height[1] = 8, height[8] = 7 → min = 7, width = 7 → area = 49
Repeat until all possible pairs are scanned via pointers
Max area found: 49

Time and Space Complexity

Time Complexity: O(n), where n is the number of lines. Each line is visited at most once by either pointer.
Space Complexity: O(1), since we only use a few variables for tracking indices and maximum area.

Edge Cases to Consider

Array with less than 2 elements → no container can be formed
All heights are equal → max area depends only on width
Decreasing or increasing height patterns → still works correctly due to pointer logic

Conclusion

The “Container With Most Water” problem is a clever application of the two-pointer technique. By reducing the problem from quadratic to linear time, this solution demonstrates how leveraging input structure and greedy decision-making leads to highly efficient algorithms.

Get Personalized Support at AlgoMap Bootcamp 💡