Container with maximum water

By | April 6, 2019

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 maximum volume of water stored between these towers. The solution for above case looks like this.

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):-

In this case, we will simply consider the area for every possible pair of the lines and find out the maximum area out of those.

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;
}

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

Method 2 (Brute force):-

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.

public int maxArea(int[] height) {

    int maxarea = 0;
    int leftPointer = 0;
    int rightPointer = height.length - 1;

    while (leftPointer < rightPointer {
        maxarea = Math.max(maxarea, Math.min(height[leftPointer], height[rightPointer]) 
                    * (rightPointer - leftPointer));

        // Update the pointer based on the lower height
        if (height[leftPointer] < height[rightPointer])
            leftPointer++;
        else
            rightPointer--;
    }
    return maxarea;
}

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

A working solution can be found here. https://ideone.com/tDxLAT

 

Author: nikoo28

a tech-savvy guy and a design buff...

Enclose codes in [code lang="C"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.