11. Container With Most Water

📝 Problem Details

• Title: 11. Container With Most Water
• Link: https://leetcode.com/problems/container-with-most-water/
• Difficulty: Medium
• Tags/Categories: Two-Pointers Greedy

input array heights where heights[i] represents the height of a vertical line at position i find two lines that together with the x-axis form a container that holds the most water return the maximum area the container can store

💭What Were My Initial Thoughts?

• The brute force approach would be to check every possible pair of heights (O(n²)), but this is inefficient.
• The problem can be solved optimally using the two-pointer technique.
• Since the amount of water depends on the shorter height and the distance between the two heights, we should try to maximize both.

💡 Explanation of Solution

Two-Pointer Approach

1. Initialize two pointers:

   • i = 0 (leftmost height)
   • j = n - 1 (rightmost height)
   • maxArea = 0 (to track the maximum area found)

2. While i < j:

   • Compute currArea = (j - i) * min(height[i], height[j]).
   • Update maxArea = max(maxArea, currArea).
   • Move the pointer pointing to the shorter height:
     • If height[i] < height[j], increment i++ (try a potentially taller height).
     • Otherwise, decrement j--.

3. Return maxArea after processing all valid containers.

⌛ Complexity Analysis

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

💻 Implementation of Solution

class Solution {
public:
    int maxArea(vector<int>& height) {
        int i=0, j = height.size()-1, maxArea = 0;
    
        while(i < j) {
            int currArea = (j-i) * min(height[i], height[j]);
            maxArea = max(currArea, maxArea);
 
            if(height[i] < height[j]) i++;
            else j--;
        }
 
        return maxArea;
    }
};