Compute the max. water trapped by a pair of vertical lines

Problem

An array of integers naturally defines a set of lines parallel to the Y-axis, starting from x = 0 as illustrated in the figure above. The goal of this problem is to find the pair of lines that together with the X-axis "trap" the most water.

Note: You may not slant the container and n is at least 2.

Input

• height: an array of integers that represent the water level

Approach

The brute force solution is fairly straightforward: calculate every sub-rectangle in the array and record the area of that sub-rectangle, only if the area is the greatest seen so far. This is \(O(n^3)\) in time complexity, which is expensive.

Another approach is to use divide-and-conquer, by recursively looking at the left half of the water and the right half of the water. This is slightly better, but still we can do better.

This problem can be solved linearly. However the intuition may be a bit tricky. Normally, one would try to solve the problem with starting from \(x = 0\) and iterating through the end of the array by incrementing \(x\). The issue with this approach is that it's difficult to determine where to start a new rectangle. If \(n\) is the number of water levels given, and \(i\) is the current index we are looking at, how can we tell if \(height_{i}\) is the start of a sub-rectangle that contains the max. amount of water? We usually can't, unless we decide to backtrack our steps; but this operation becomes costly.

Instead, we can use a greedy approach and consider iterating through the array using two pointers instead of one; one from the start \(heights\) and one from the back \(heightb\). If the \(heightb\) water level is much higher than the \(heights\) water level, then we know that the \(height{s+1}\) water level may have a chance of producing the max. amount of water. Otherwise if the \(heightb\) water level is much smaller than \(heights\), then \(height{b-1}\) may give us a chance of producing the max. amount of water. By starting our rectangle with the widest possible and recording the area of the rectangle as we condense it, we can obtain the max. water trapped by any sub-rectangle.

This solution has a pattern; it operates on the condition that the area from the left or right side no longer needs to be calculated as we condense and shrink the main rectangle. This algorithm is known to use a loop invariant, which means that there is a property inside a loop that is true before each iteration is executed. In this example, the property is the condition that we no longer have to look through the data points that we have visited before the condensing.

Solution

    def maxArea(self, height: 'List[int]') -> 'int':
        left, right = 0, len(height)-1
        area = 0

        while left < right:
            area = max(area, min(height[left], height[right]) * (right - left))
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1

        area = max(area, min(height[left], height[right]) * (right - left))
        return area