--- title: Container With Most Water description: Find the maximum area of water container using two-pointer technique with O(n) time complexity. date: 2024-03-14 tag: ["Medium", "Array", "Two Pointers"] author: Easy Algo premium: false percentage: 30 --- ## Problem > LeetCode link: [Container With Most Water](https://leetcode.com/problems/container-with-most-water/) ![container with most water](https://p0-xtjj-private.juejin.cn/tos-cn-i-73owjymdk6/2f3c024367b34fe0916a8d46d39e849e~tplv-73owjymdk6-jj-mark-v1:0:0:0:0:5o6Y6YeR5oqA5pyv56S-5Yy6IEAg56iL5bqP5ZGY6Ie75Y-U:q75.awebp?policy=eyJ2bSI6MywidWlkIjoiMjI0MjY1OTQ0OTMxODkwNCJ9&rk3s=e9ecf3d6&x-orig-authkey=f32326d3454f2ac7e96d3d06cdbb035152127018&x-orig-expires=1742058337&x-orig-sign=Pan%2BvIzCOuwW%2BBsVApRZ1%2FD4t%2Fw%3D) 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. Note: You may not slant the container. **Example 1:** ``` Input: height = [1,8,6,2,5,4,8,3,7] Output: 49 Explanation: The vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49. ``` **Example 2:** ``` Input: height = [1,1] Output: 1 ``` **Constraints:** ``` n == height.length 2 <= n <= 10^5 0 <= height[i] <= 10^4 ``` ## Solution **Problem Simplified:** Imagine you have a series of vertical lines of different heights. Your task is to select two lines that, together with the x-axis, form a container that can hold the maximum amount of water. The container's capacity is determined by the height of the shorter line (as water can't exceed this height) and the distance between the two lines. Your goal is to find the two lines that create the container with the largest possible capacity. **Edge Cases and Test Examples:** * **Edge Cases:** * Array length constraints (2 ≤ n ≤ 10^5) eliminate empty or single-element arrays * All elements are identical (e.g., `[5, 5, 5, 5]`) * Array contains zeros (e.g., `[0, 2, 3, 0]`) * Monotonic arrays (e.g., `[1, 2, 3, 4]` or `[4, 3, 2, 1]`) * **Test Cases:** | Input `height` | Output | |----------------|--------| | `[1, 8, 6, 2, 5, 4, 8, 3, 7]` | 49 | | `[1, 1]` | 1 | | `[4, 3, 2, 1]` | 4 | | `[1, 2, 3, 4, 5]` | 6 | | `[5, 5, 5, 5]` | 15 | | `[0, 2, 3, 0]` | 0 | **Solution Analysis:** | Approach | Advantages | Disadvantages | Time Complexity | Space Complexity | |----------|------------|---------------|----------------|------------------| | Brute Force | Simple to understand | Inefficient for large inputs | O(n²) | O(1) | | Two Pointers | Optimal time complexity, efficient | Requires understanding of pointer movement strategy | O(n) | O(1) | * **Complexity Analysis:** * Time Complexity: Evaluates how runtime scales with input size * Space Complexity: Evaluates how memory usage scales with input size * **Recommended Approach:** * Two Pointers method is optimal, offering the best time complexity while maintaining constant space usage **Python Implementation:** * **Version 1: With Detailed Comments** ```python def max_area(height): """ Calculate the maximum water container capacity from the height array. Args: height: Array of integers representing line heights Returns: Integer representing maximum water capacity """ left = 0 # Left pointer at start right = len(height) - 1 # Right pointer at end max_water = 0 # Track maximum water capacity while left < right: # Calculate current container capacity current_water = min(height[left], height[right]) * (right - left) # Update maximum capacity if current is larger max_water = max(max_water, current_water) # Move pointer at shorter line inward # Moving the shorter line gives potential for larger area if height[left] < height[right]: left += 1 # Move left pointer right else: right -= 1 # Move right pointer left return max_water ``` * **Version 2: Clean Implementation** ```python def max_area(height): left = 0 right = len(height) - 1 max_water = 0 while left < right: current_water = min(height[left], height[right]) * (right - left) max_water = max(max_water, current_water) if height[left] < height[right]: left += 1 else: right -= 1 return max_water ``` **Step-by-Step Execution:** Let's walk through the solution with input `height = [1, 8, 6, 2, 5, 4, 8, 3, 7]`: 1. **Initialization:** * `left = 0` points to `height[0] = 1` * `right = 8` points to `height[8] = 7` * `max_water = 0` 2. **Iteration Process:** * **First Iteration:** * `current_water = min(1, 7) * (8 - 0) = 1 * 8 = 8` * `max_water = max(0, 8) = 8` * Since `height[left] < height[right]` (1 < 7), increment `left` to 1 * **Second Iteration:** * `current_water = min(8, 7) * (8 - 1) = 7 * 7 = 49` * `max_water = max(8, 49) = 49` * Since `height[left] > height[right]` (8 > 7), decrement `right` to 7 * **Subsequent Iterations:** * Continue until pointers meet, updating `max_water` as needed 3. **Result:** * Return `max_water = 49` as the maximum container capacity