Container with most water#

Levels: level-2

Data structures: array

Practice Link#

LeetCode

Description#

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 and n is at least 2.

Example#

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

Python Solution#

 1class Solution(object):
 2    def maxArea(self, height):
 3        """
 4        :type height: List[int]
 5        :rtype: int
 6        """
 7        if not height:
 8            return -1
 9        l = 0
10        h = len(height) - 1
11        if h < 1:
12            return -1
13        maxarea = -1
14        sidel = h
15        while l < h:
16            if height[l] < height[h]:
17                sidew = height[l]
18                l += 1
19            else:
20                sidew = height[h]
21                h -= 1
22            a = sidew * sidel
23            if a > maxarea:
24                maxarea = a
25            sidel -= 1
26        return maxarea
27
28
29in_arrs = [
30    [1, 8, 6, 2, 5, 4, 8, 3, 7],
31    [1],
32    [],
33    None,
34]
35
36exp_out = [
37    49,
38    -1,
39    -1,
40    -1,
41]
42
43if __name__ == "__main__":
44
45    sol = Solution()
46    for idx, nin in enumerate(in_arrs):
47        resout = sol.maxArea(nin)
48        print(nin, resout, exp_out[idx], resout == exp_out[idx])