Container With Most Water

Array, Two Pointers

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:

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

Assumptions:

• There is no number calculation overflow.

• There is no any negative value element.

Questions to Clarify:

• What would be the size of the input array?

Solutions

As per the problem, we need to find out the maximum area that can hold most water, and the mathematical formula for calculate area is (Length*Width). In this problem, length is the value of the element, and width is the index gap between two elements.

Here, the area calculation formula for this problem is:

area = min(leftElement,rightElement)*(rightElementIndex-leftElementIndex)

Approach – Brute Force Technique

Run two nested loops to calculate the area between two elements and compare it with the previous area value. If it is greater than the previous one, then set it to the maximum area.

Steps

1. The algorithm starts by initializing maxArea to 0. This variable will keep track of the maximum area found so far.

2. It then checks if the height array is not null and has at least 2 elements. If not, it returns maxArea (which is 0) immediately, as you can't form a container with less than 2 lines.

3. The algorithm then enters a nested loop. The outer loop (i) goes from 0 to the length of the height array. The inner loop (j) goes from i + 1 to the length of the height array. This way, every pair of lines is considered exactly once.

4. For each pair of lines, it calculates the area of the container they would form. This is done by taking the minimum of the heights of the two lines (since the water would overflow from the shorter line) and multiplying it by the distance between the lines (j - i).

5. If the calculated area is greater than maxArea, it updates maxArea with the new area.

6. After considering all pairs of lines, it returns maxArea, which is the maximum area of water that can be contained.

public class Solution
{
    public int MaxArea(int[] height)
    {
        int maxArea = 0;

        if (height != null && height.Length >= 2)
        {
            for (int i = 0; i < height.Length; i++)
            {
                for (int j = i + 1; j < height.Length; j++)
                {
                    int area = Math.Min(height[i], height[j]) * (j - i);
                    if (area > maxArea)
                    {
                        maxArea = area;
                    }
                }
            }
        }
        return maxArea;
    }
}

Complexity

• Time complexity: O(N^2)

• Space complexity: O(1)

Approach – Two Pointers Technique

This problem can be solved using a two-pointer approach. Initialize two pointers, one at the beginning of the array (left) and one at the end of the array ('right'), calculate the area between them, and move the smaller pointer forward or backward responsively.

Steps

1. The algorithm starts by initializing maxArea to 0. This variable will keep track of the maximum area found so far.

2. It then checks if the height array is not null and has at least 2 elements. If not, it returns maxArea (which is 0) immediately, as you can't form a container with less than 2 lines.

3. It initializes two pointers, left and right, to the start and end of the array respectively.

4. It enters a loop that continues until left and right meet. In each iteration of the loop, it does the following:

   • It calculates the area of the container formed by the lines at left and right. This is done by taking the minimum of the heights of the two lines (since the water would overflow from the shorter line) and multiplying it by the distance between the lines (right - left).

   • If the calculated area is greater than maxArea, it updates maxArea with the new area.

   • It then decides which pointer to move. If the height of the line at left is less than the height of the line at right, it moves the left pointer one step to the right. Otherwise, it moves the right pointer one step to the left. The reason for this is that moving the pointer with the smaller height gives us a chance to find a higher line that can potentially lead to a larger area.

5. After the loop ends, it returns maxArea, which is the maximum area of water that can be contained.

public class Solution
{
    public int MaxArea(int[] height)
    {
        int maxArea = 0;

        if (height != null && height.Length >= 2)
        {
            int left = 0;
            int right = height.Length - 1;
            while (left < right)
            {
                var area = Math.Min(height[left], height[right]) * (right - left);
                if (area > maxArea)
                {
                    maxArea = area;
                }
                if (height[left] < height[right])
                {
                    left++;
                }
                else
                {
                    right--;
                }
            }
        }
        return maxArea;
    }
}

Complexity

• Time complexity: O(N)

• Space complexity: O(1)