# Container With Most Water **Difficulty:** MEDIUM [External](https://leetcode.com/problems/container-with-most-water) Canonical: https://scaleengineer.com/dsa/problems/container-with-most-water **Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Greedy](https://scaleengineer.com/dsa/patterns/greedy) **Data structures:** Array **Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Accolite](https://scaleengineer.com/companies/accolite), [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Atlassian](https://scaleengineer.com/companies/atlassian), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [ByteDance](https://scaleengineer.com/companies/bytedance), [Deloitte](https://scaleengineer.com/companies/deloitte), [Flipkart](https://scaleengineer.com/companies/flipkart), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Infosys](https://scaleengineer.com/companies/infosys), [Intel](https://scaleengineer.com/companies/intel), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [Mastercard](https://scaleengineer.com/companies/mastercard), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Myntra](https://scaleengineer.com/companies/myntra), [Nutanix](https://scaleengineer.com/companies/nutanix), [Oracle](https://scaleengineer.com/companies/oracle), [PayPal](https://scaleengineer.com/companies/paypal), [Paytm](https://scaleengineer.com/companies/paytm), [SAP](https://scaleengineer.com/companies/sap), [Samsung](https://scaleengineer.com/companies/samsung), [ServiceNow](https://scaleengineer.com/companies/servicenow), [Snowflake](https://scaleengineer.com/companies/snowflake), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Visa](https://scaleengineer.com/companies/visa), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Wix](https://scaleengineer.com/companies/wix), [Yahoo](https://scaleengineer.com/companies/yahoo), [Yandex](https://scaleengineer.com/companies/yandex), [Zoho](https://scaleengineer.com/companies/zoho), [tcs](https://scaleengineer.com/companies/tcs), [Zopsmart](https://scaleengineer.com/companies/zopsmart), [Salesforce](https://scaleengineer.com/companies/salesforce), [Tesla](https://scaleengineer.com/companies/tesla), [Citadel](https://scaleengineer.com/companies/citadel), [RBC](https://scaleengineer.com/companies/rbc), [Coveo](https://scaleengineer.com/companies/coveo), [HSBC](https://scaleengineer.com/companies/hsbc), [HashedIn](https://scaleengineer.com/companies/hashedin), [Lenskart](https://scaleengineer.com/companies/lenskart), [Miro](https://scaleengineer.com/companies/miro), [QBurst](https://scaleengineer.com/companies/qburst), [Sprinklr](https://scaleengineer.com/companies/sprinklr), [Zoom](https://scaleengineer.com/companies/zoom), [oyo](https://scaleengineer.com/companies/oyo), [razorpay](https://scaleengineer.com/companies/razorpay) --- ## Problem 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_. **Notice** that you may not slant the container. **Example 1:** ![](https://assets.glich.co/dsa/container-with-most-water/image0.jpg) **Input:** height = [1,8,6,2,5,4,8,3,7] **Output:** 49 **Explanation:** The above 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 <= 105` * `0 <= height[i] <= 104` # Approaches ## Brute Force Approach The most straightforward solution is to consider every possible pair of vertical lines and calculate the area of the container they form. We can then keep track of the maximum area found among all pairs. **Time:** O(n^2) · **Space:** O(1) **Pros:** Simple to understand and implement.; Guaranteed to find the correct answer as it checks every possibility. **Cons:** Very inefficient due to its quadratic time complexity.; Will likely result in a 'Time Limit Exceeded' error on platforms like LeetCode for large input sizes. ### Explanation This method involves using two nested loops to iterate through all possible pairs of lines. The outer loop selects the first line (`i`), and the inner loop selects the second line (`j`), where `j` is always to the right of `i`. For each pair `(i, j)`, the area is calculated as the product of the distance between the lines (`j - i`) and the height of the shorter line (`min(height[i], height[j])`). We maintain a variable, `maxArea`, which is updated whenever a larger area is found. After checking all pairs, `maxArea` will hold the result. ```java class Solution { public int maxArea(int[] height) { int maxArea = 0; int n = height.length; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int currentHeight = Math.min(height[i], height[j]); int currentWidth = j - i; int currentArea = currentHeight * currentWidth; maxArea = Math.max(maxArea, currentArea); } } return maxArea; } } ``` ### Algorithm - Initialize a variable `maxArea` to 0. - Use a for loop to iterate from the first line `i = 0` to the second to last line `n-2`. - Inside this loop, use another for loop to iterate from `j = i + 1` to the last line `n-1`. - For each pair of lines `(i, j)`, calculate the area: `area = Math.min(height[i], height[j]) * (j - i)`. - Compare this `area` with `maxArea` and update `maxArea` if the current `area` is larger: `maxArea = Math.max(maxArea, area)`. - After the loops complete, return `maxArea`. ## Two Pointer Approach A more efficient solution uses the two-pointer technique. We start with the widest possible container, using pointers at the very beginning and very end of the array. Then, we iteratively narrow the container by moving one of the pointers, always aiming to find a taller bounding line to compensate for the reduced width. **Time:** O(n) · **Space:** O(1) **Pros:** Highly efficient with a linear time complexity.; Uses constant extra space.; Optimal solution for this problem. **Cons:** The logic for moving the pointers might be slightly less intuitive to grasp initially compared to the brute-force method. ### Explanation We initialize two pointers, `left` at index 0 and `right` at the last index `n-1`. These two pointers represent the boundaries of the container. In each step, we calculate the area formed by the lines at `left` and `right`. The area is `min(height[left], height[right]) * (right - left)`. We update our maximum area found so far. The key insight is how to move the pointers. The width `(right - left)` will always decrease. To have a chance of finding a larger area, we must increase the height of the container, which is limited by the shorter of the two lines. Therefore, it's always optimal to move the pointer corresponding to the shorter line inward. If `height[left] < height[right]`, we move `left` one step to the right. Otherwise, we move `right` one step to the left. This process continues until the pointers meet or cross (`left >= right`). This strategy works because we are systematically eliminating the shorter line, which cannot be part of a better container with any line within the current `left` and `right` boundaries. ```java class Solution { public int maxArea(int[] height) { int maxArea = 0; int left = 0; int right = height.length - 1; while (left < right) { int currentHeight = Math.min(height[left], height[right]); int currentWidth = right - left; int currentArea = currentHeight * currentWidth; maxArea = Math.max(maxArea, currentArea); if (height[left] < height[right]) { left++; } else { right--; } } return maxArea; } } ``` ### Algorithm - Initialize `maxArea = 0`, `left = 0`, and `right = n - 1`. - Loop as long as `left < right`. - Calculate the current area: `area = Math.min(height[left], height[right]) * (right - left)`. - Update `maxArea`: `maxArea = Math.max(maxArea, area)`. - If `height[left]` is less than `height[right]`, increment `left`. - Otherwise, decrement `right`. - After the loop finishes, return `maxArea`. # Solutions ### CSharp ```csharp public class Solution { public int MaxArea(int[] height) { int i = 0, j = height.Length - 1; int ans = 0; while (i < j) { int t = Math.Min(height[i], height[j]) * (j - i); ans = Math.Max(ans, t); if (height[i] < height[j]) { ++i; } else { --j; } } return ans; } } ``` ### Java ```java class Solution { public int maxArea(int[] height) { int i = 0, j = height.length - 1; int ans = 0; while (i < j) { int t = Math.min(height[i], height[j]) * (j - i); ans = Math.max(ans, t); if (height[i] < height[j]) { ++i; } else { --j; } } return ans; } } ``` ### JavaScript ```javascript /** * @param {number[]} height * @return {number} */ var maxArea = function ( height, ) { let i = 0; let j = height.length - 1; let ans = 0; while (i < j) { const t = Math.min(height[i], height[j]) * (j - i); ans = Math.max(ans, t); if (height[i] < height[j]) { ++i; } else { --j; } } return ans; }; ``` ### CPP ```cpp class Solution { public: int maxArea(vector &height) { int i = 0, j = height.size() - 1; int ans = 0; while (i < j) { int t = min(height[i], height[j]) * (j - i); ans = max(ans, t); if (height[i] < height[j]) { ++i; } else { --j; } } return ans; } }; ``` ### Python ```python class Solution: def maxArea(self, height: List[int]) -> int: i, j = 0, len(height) - 1 ans = 0 while i < j: t = (j - i) * min(height[i], height[j]) ans = max(ans, t) if height[i] < height[j]: i += 1 else: j -= 1 return ans ```