Container with maximum water

Question: Let us suppose we have a two dimensional plane where the the length of lines determine the height of a container. We need to determine the maximum capacity of water this kind of an arrangement can hold. The heights are represented by an array.

Input: [1, 8, 6, 2, 5, 4, 8, 3, 7]

Output: 49

Let us try to visualize the problem at hand diagrammatically. Let the array be represented as:

If we try to pour water from the top in the entire arrangement you can visualize that only
– 1 unit of water would be retained between tower 1 and 2.
– 6 units between 2 and 3.
– 2 units between 3 and 4
and so on.

In a way each pair of towers form a container with walls. We need to find the container with maximum water volume stored between these towers. The solution for above case will be:

Which forms a total of 49 units of water. (9 - 2) * height (7) = 49

Towers 2 and 7 can hold a maximum of (7 - 2) * 8 = 40 units. So it is not the maximum.

Let us see how we can approach the problem.

Method 1 (Brute force):-

A brute force solution to this problem is pretty obvious. We can start with the first stick and try to form a container with every other stick. Once this iteration is complete, we can start with the second stick and repeat the process. We just keep a track of the maximum area found so far.

This method works perfectly, but it will consume a lot of time if the array size is very large.

public int maxArea(int[] height) {

    int maxarea = 0;

    for (int i = 0; i < height.length; i++) {
        for (int j = i + 1; j < height.length; j++) {
            maxarea = Math.max(maxarea, Math.min(height[i], height[j]) * (j - i));
        }
    }
    return maxarea;
}
Code language: Java (java)

Time Complexity:- O(n^2)
Space Complexity:- O(1)

Method 2 (Efficient Solution):-

We need to look at 2 important aspects of the problem.

• It is very obvious that the height of the maximum container would be determined by the short tower.
• The farther the two tower, more would be the area of the container.

Algorithm

• Start with two pointers. One from the start(A) and one from the end(B).
• Keep a memory of the maximum area possible.
• Measure the possible area between the two towers and update maxarea.
• If the tower on the left is a shorter one, move pointer A to the right, to look for a bigger tower.
• If the tower on the right is a shorter one, move pointer B to the left, to look for a bigger tower.
• At each instant calculate the area and update the maxarea possible.
• When both the pointers A and B meet, we should have our answer.

This approach works because if we try to move away from the longer tower, we are definitely moving towards a shorter area since the width decreases and we are limited in area by the height of the shorter tower. Hence, it would be beneficial to move from the shorter tower in a hope of maximizing the area.

Code:

  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(area, maxArea);

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

    return maxArea;
  }
Code language: Java (java)

Time Complexity: O(n) where N is the length of array.
Space Complexity: O(1), the space used by our int variables.

You can also find the complete code, along with test-cases on Github.

Video Explanation: