Find the maximum possible area

Question

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container.

One solution could be that we take each and every line and find area with every line. This takes O(n^2). Not time efficient.

Another solution could be using DP to find the maximum area for every index, and then at index n, we will get the maximum area. I think it's O(n).

Could there be more better solutions?

Answer 1

int maxArea(vector<int> &height) {
    int ret = 0;
    int left = 0, right = height.size() - 1;
    while (left < right) {
        ret = max(ret, (right - left) * min(height[left], height[right]));
        if (height[left] <= height[right])
            left++;
        else
            right--;
    }
    return ret;
}

Answer 2

Many people here are mistaking this problem to maximal rectangle problem, which is not the case.

Solution

1. Delete all the elements aj such that ai >= aj =< ak and i > j < k. This can be done in linear time.
   1. Find the maximum value am
   2. Let as = a1
   3. For j = 2 through m-1, if as >= aj, delete aj, else as = aj
   4. Let as = an
   5. For j = n-1 through m+1, if as >= aj, delete aj, else as = aj
2. Notice that the resulting values look like a pyramid, that is, all the elements on the left of the maximum are strictly increasing and on the right are strictly decreasing.
3. i=1, j=n. m is location of max.
4. While i<=m and j>=m
   1. Find area between ai and aj and keep track of the max
   2. If ai < aj, i+=1, else j-=1

Complexity is linear (O(n))

Answer 3

Here is an implementation with Java:

Basic idea is to use two pointers from front and back, and calculate the area along the way.

public int maxArea(int[] height) {
    int i = 0, j = height.length-1;
    int max = Integer.MIN_VALUE;

    while(i < j){
        int area = (j-i) * Math.min(height[i], height[j]);
        max = Math.max(max, area);
        if(height[i] < height[j]){
            i++;
        }else{
            j--;
        }
    }

    return max;
}

Answer 4

Here is a clean Python3 solution. The runtime for this solution is O(n). It is important to remember that the area formed between two lines is determined by the height of the shorter line and the distance between the lines.

def maxArea(height):
    """
    :type height: List[int]
    :rtype: int
    """
    left = 0
    right = len(height) - 1
    max_area = 0
    while (left < right):
        temp_area = ((right - left) * min(height[left], height[right]))
        if (temp_area > max_area):
            max_area = temp_area
        elif (height[right] > height[left]):
            left = left + 1
        else:
            right = right - 1
    return max_area

Answer 5

This problem can be solved in linear time.

1. Construct a list of possible left walls (position+height pairs), in order from highest to lowest. This is done by taking the leftmost possible wall and adding it to the list, then going through all possible walls, from left to right, and taking every wall that is larger than the last wall added to the list. For example, for the array

   2 5 4 7 3 6 2 1 3
   

   your possible left walls would be (pairs are (pos, val)):

   (3, 7) (1, 5) (0, 2)
   

2. Construct a list of possible right walls in the same way, but going from right to left. For the above array the possible right walls would be:

   (3, 7) (5, 6) (8, 3)
   

3. Start your water level as high as possible, that is the minimum of heights of the walls at the front of the two lists. Calculate the total volume of water using those walls (it might be negative or zero, but that is ok), then drop the water level by popping an element off of one of the lists such that the water level drops the least. Calculate the possible water volume at each of these heights and take the max.

Running this algorithm on these lists would look like this:

L: (3, 7) (1, 5) (0, 2)  # if we pop this one then our water level drops to 5
R: (3, 7) (5, 6) (8, 3)  # so we pop this one since it will only drop to 6
Height = 7
Volume = (3 - 3) * 7 = 0
Max = 0

L: (3, 7) (1, 5) (0, 2)  # we pop this one now so our water level drops to 5
R: (5, 6) (8, 3)         # instead of 3, like if we popped this one
Height = 6
Volume = (5 - 3) * 6 = 12
Max = 12

L: (1, 5) (0, 2)
R: (5, 6) (8, 3)
Height = 5
Volume = (5 - 1) * 5 = 20
Max = 20


L: (1, 5) (0, 2)
R: (8, 3)
Height = 3
Volume = (8 - 1) * 3 = 21
Max = 21

L: (0, 2)
R: (8, 3)
Height = 2
Volume = (8 - 0) * 2 = 16
Max = 21

Steps 1, 2, and 3 all run in linear time, so the complete solution also takes linear time.

Answer 6

The best answer is by Black_Rider, however they did not provide an explanation.

I've found a very clear explanation on this blog. Shortly, it goes as follows:

Given array height of length n:

1. Start with the widest container you can, i.e. from left side at 0 to right side at n-1.

2. If a better container exists it will be narrower, so its both sides must be higher than the lower of currently chosen sides.

3. So, change left to (left+1) if height[left] < height[right], otherwise change right to (right-1).

4. Calculate new area, if it's better than what you have so far, replace.

5. If left < right, start over from 2.

My implementation in C++:

int maxArea(vector<int>& height) {
    auto current = make_pair(0, height.size() - 1);
    auto bestArea = area(height, current);

    while (current.first < current.second) {
        current = height[current.first] < height[current.second]
            ? make_pair(current.first + 1, current.second)
            : make_pair(current.first, current.second - 1);

        auto nextArea = area(height, current);
        bestArea = max(bestArea, nextArea);
    }

    return bestArea;
}

inline int area(const vector<int>& height, const pair<int, int>& p) {
    return (p.second - p.first) * min(height[p.first], height[p.second]);
}

Answer 7

This problem is a simpler version of The Maximal Rectangle Problem. The given situation can be view as a binary matrix. Consider the rows of the matrix as X-axis and columns as Y-axis. For every element a[i] in the array, set

Matrix[i][0] = Matrix[i][1] = ..... = Matrix[i][a[i]] = 1

For e.g - For a[] = { 5, 3, 7, 1}, our binary matrix is given by:

1111100
1110000
1111111
1000000