Pular para o conteúdo principal

Container With Most Water

You are building a pool in your backyard and want to create the largest pool possible. The largest pool is defined as the pool that holds the most water. The workers you hired to dig the hole for your pool didn't do a great job and because of this the depths of the pool at different areas are not equal. Given an integer array of non-negative integers that represents a histogram of the different heights at each position of the hole for your pool, return the largest pool you can create.

Note: The water volume between two positions i and j is calculated as min(height[i], height[j]) * (j - i).

Example(s)​

Example 1:

Input: heights = [1, 4, 4, 8, 2]
Output: 8
Explanation: 
You can build your largest pool between indices 1 and 3 (inclusive).
Water volume = min(4, 8) * (3 - 1) = 4 * 2 = 8

Example 2:

Input: heights = [1, 8, 6, 2, 5, 4, 8, 3, 7]
Output: 49
Explanation:
The largest pool is between indices 1 and 8.
Water volume = min(8, 7) * (8 - 1) = 7 * 7 = 49

Example 3:

Input: heights = [1, 1]
Output: 1
Explanation:
Water volume = min(1, 1) * (1 - 0) = 1 * 1 = 1

Example 4:

Input: heights = [2, 3, 4, 5, 18, 17, 6]
Output: 17
Explanation:
The largest pool is between indices 1 and 6.
Water volume = min(3, 6) * (6 - 1) = 3 * 5 = 15
Wait, let me recalculate... Actually between indices 4 and 5:
Water volume = min(18, 17) * (5 - 4) = 17 * 1 = 17

Solution​

The solution uses the two-pointer technique:

  1. Start with widest container: left = 0, right = n - 1
  2. Calculate area: min(height[left], height[right]) * (right - left)
  3. Move pointer with smaller height: The area is limited by the shorter bar, so moving the taller bar inward can only decrease the area
  4. Track maximum: Keep track of the maximum area seen so far
  5. Continue until pointers meet

Key Insight: Always move the pointer with the smaller height because:

  • The area is limited by the shorter bar
  • Moving the taller bar inward can only decrease the width, and the height won't increase (still limited by shorter bar)
  • Moving the shorter bar might find a taller bar, potentially increasing the area

JavaScript Solution

/**
* Find the container with the most water
* @param {number[]} heights - Array of non-negative integers representing heights
* @return {number} - Maximum water volume
*/
function maxArea(heights) {
let left = 0;
let right = heights.length - 1;
let maxWater = 0;

while (left < right) {
  // Calculate current area
  const width = right - left;
  const height = Math.min(heights[left], heights[right]);
  const area = width * height;
  
  // Update maximum
  maxWater = Math.max(maxWater, area);
  
  // Move pointer with smaller height
  if (heights[left] < heights[right]) {
    left++;
  } else {
    right--;
  }
}

return maxWater;
}

// Test cases
console.log('Example 1:', maxArea([1, 4, 4, 8, 2])); // 8
console.log('Example 2:', maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7])); // 49
console.log('Example 3:', maxArea([1, 1])); // 1
console.log('Example 4:', maxArea([2, 3, 4, 5, 18, 17, 6])); // 17
console.log('Test 5:', maxArea([1, 2, 1])); // 2
Output:
Click "Run Code" to execute the code and see the results.

Brute Force Solution​

For comparison, here's the brute force approach (O(n²)):

/**
 * Brute force solution - O(n²) time
 * Check all possible pairs
 */
function maxAreaBruteForce(heights) {
  let maxWater = 0;
  const n = heights.length;
  
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      const width = j - i;
      const height = Math.min(heights[i], heights[j]);
      const area = width * height;
      maxWater = Math.max(maxWater, area);
    }
  }
  
  return maxWater;
}

Test the Brute Force Solution​

JavaScript Brute Force Solution

/**
* Brute force solution - O(n²) time
* Check all possible pairs
*/
function maxAreaBruteForce(heights) {
let maxWater = 0;
const n = heights.length;

for (let i = 0; i < n; i++) {
  for (let j = i + 1; j < n; j++) {
    const width = j - i;
    const height = Math.min(heights[i], heights[j]);
    const area = width * height;
    maxWater = Math.max(maxWater, area);
  }
}

return maxWater;
}

// Test cases
console.log('Example 1:', maxAreaBruteForce([1, 4, 4, 8, 2])); // 8
console.log('Example 2:', maxAreaBruteForce([1, 8, 6, 2, 5, 4, 8, 3, 7])); // 49
console.log('Example 3:', maxAreaBruteForce([1, 1])); // 1
console.log('Example 4:', maxAreaBruteForce([2, 3, 4, 5, 18, 17, 6])); // 17
Output:
Click "Run Code" to execute the code and see the results.

Complexity​

  • Time Complexity: O(n) - Where n is the length of the heights array. We traverse the array once with two pointers.
  • Space Complexity: O(1) - Only using a constant amount of extra space for variables.

Approach​

The solution uses the two-pointer technique with a greedy strategy:

  1. Initialize pointers: Start with left = 0 and right = n - 1 (widest possible container)
  2. Calculate area: For current positions, calculate min(height[left], height[right]) * (right - left)
  3. Update maximum: Keep track of the maximum area seen
  4. Move pointer: Always move the pointer with the smaller height
    • If height[left] < height[right]: move left right
    • Otherwise: move right left
  5. Terminate: Continue until left >= right

Why This Works​

The key insight is that we should always move the pointer with the smaller height:

Proof by contradiction:

  • Suppose we have height[left] < height[right]
  • Current area = height[left] * (right - left)
  • If we move right left:
    • New width = (right - 1) - left (decreased)
    • New height ≤ height[left] (still limited by shorter bar)
    • New area ≤ current area (both width and height can't increase)
  • If we move left right:
    • New width = right - (left + 1) (decreased)
    • New height might be > height[left] (could find taller bar)
    • New area might be > current area

Therefore, moving the shorter pointer is the only way to potentially find a larger area.

Key Insights​

  • Two-pointer technique is optimal for this problem
  • Greedy strategy: Always move the pointer that limits the area
  • Start wide: Beginning with the widest container gives us the best starting point
  • No need to check all pairs: The greedy approach eliminates many possibilities
  • O(n) solution: Much better than O(n²) brute force

Step-by-Step Example​

Let's trace through Example 1: heights = [1, 4, 4, 8, 2]

Initial: left = 0, right = 4
heights = [1, 4, 4, 8, 2]
          ↑           ↑
        left        right

Step 1:
  area = min(1, 2) * (4 - 0) = 1 * 4 = 4
  maxWater = 4
  height[left] (1) < height[right] (2) → left++

Step 2: left = 1, right = 4
  area = min(4, 2) * (4 - 1) = 2 * 3 = 6
  maxWater = 6
  height[left] (4) > height[right] (2) → right--

Step 3: left = 1, right = 3
  area = min(4, 8) * (3 - 1) = 4 * 2 = 8
  maxWater = 8
  height[left] (4) < height[right] (8) → left++

Step 4: left = 2, right = 3
  area = min(4, 8) * (3 - 2) = 4 * 1 = 4
  maxWater = 8 (no update)
  height[left] (4) < height[right] (8) → left++

Step 5: left = 3, right = 3 → break

Final answer: 8

Edge Cases​

  • Two elements: Return the area between them
  • All same height: Works correctly, area depends on width
  • Ascending heights: Maximum area is at the ends
  • Descending heights: Maximum area is at the ends
  • One element: Not applicable (need at least 2)
  • Empty array: Return 0

Optimization Note​

When heights are equal, we can move either pointer. However, moving both doesn't help because:

  • If we move only one, we'll eventually check the other combination
  • Moving both would skip valid combinations
  • The current approach (move one at a time) is correct
  • Trapping Rain Water: Similar concept but different problem (water can be trapped at multiple positions)
  • Largest Rectangle in Histogram: Different problem but also involves histograms

Takeaways​

  • Two-pointer technique is powerful for array problems
  • Greedy strategy can lead to optimal solutions
  • Start with widest container maximizes initial area
  • Always move the limiting pointer is the key insight
  • O(n) solution is possible with careful analysis of the problem structure