Container With Most Water medium

Problem Statement

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the i^th 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:

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

Steps and Explanation

The problem asks us to find the maximum area formed by two lines and the x-axis. The area of a container is determined by the shorter of the two lines (height) multiplied by the distance between them (width). A brute-force approach would check all possible pairs of lines, which is O(n²). However, a more efficient approach using two pointers can solve this in O(n) time.

Here's the algorithm:

1. Initialization: Use two pointers, left and right, pointing to the beginning and end of the height array, respectively. Initialize maxArea to 0.

2. Iteration: While left < right:

   • Calculate the current area: area = min(height[left], height[right]) * (right - left).
   • Update maxArea: maxArea = max(maxArea, area).
   • Move the pointer: Move the pointer that points to the shorter line inwards. This is because moving the taller line inwards can only potentially decrease the area (the width will decrease, and the height is already limited by the shorter line). If height[left] < height[right], increment left; otherwise, decrement right.

3. Return: After iterating through all possible pairs using this two-pointer approach, return maxArea.

This approach is efficient because it avoids redundant calculations. By moving the shorter line inwards, we are guaranteed to explore all possible pairs while maintaining the efficiency.

Code (C#)

using System;

public class Solution {
    public int MaxArea(int[] height) {
        int left = 0;
        int right = height.Length - 1;
        int maxArea = 0;

        while (left < right) {
            int area = Math.Min(height[left], height[right]) * (right - left);
            maxArea = Math.Max(maxArea, area);

            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }

        return maxArea;
    }
}

Complexity

• Time Complexity: O(n), where n is the length of the height array. We iterate through the array using two pointers only once.
• Space Complexity: O(1). We use a constant amount of extra space to store variables like left, right, and maxArea.