# Container With Most Water — Python(Day 40)

Today’s problem is another favorite among FAANG interviewers. It is on Arrays topic. Let us look into the question.

11. Container With Most Water

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 the line `i` is at `(i, ai)` and `(i, 0)`. Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

Notice that you may not slant the container.

Example 1:

`Input: height = [1,8,6,2,5,4,8,3,7]Output: 49Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.`

Example 2:

`Input: height = [1,1]Output: 1`

Example 3:

`Input: height = [4,3,2,1,4]Output: 16`

Example 4:

`Input: height = [1,2,1]Output: 2`

Constraints:

• `n = height.length`
• `2 <= n <= 3 * 104`
• `0 <= height[i] <= 3 * 104`

The brute force approach is to create a subset of containers and check which container can hold the maximum water.

To create a subset of containers from the given list of the number we would require two for loops, The first for loop will hold the start of the container and the second for loop will hold the end of the container.

To find the amount of water a container holds, we need to find the minimum height among left and right wall, this is the height of the container. The distance between left and right is the breadth of the container. The total water a container can hold is

min(height[left], height[right])*(right-left)

Let us look into the code snippet.

`class MaxWaterHolder:    def maxArea(self, height: List[int]) -> int:        max_water = 0        for left in range(len(height)-1):            for right in range(left+1, len(height)):                max_water = max(max_water,min(height[left], height[right])*(right -left))        return max_water`

Complexity analysis.

Time Complexity

We are creating a subset of each possible container from the list of heights provided to us. Hence the time complexity is O(N²).

Space Complexity.

We are not using any extra data structure to store anything. Hence the space complexity is O(1).

Do we have to create a subset of containers each time? Can we think of using two pointers, one starts from the 0th index and the second from the end to solve this problem?

Initialize left as index 0, right as the index at the end of the list.

Check the minimum height among the left index and right index. Multiply it with the distance between left and right. This would give the amount of water that the container will hold. Maximum among these values have to be selected. If the height at the left pointer’s index is smaller than the right, then the left pointer will move ahead else right pointer will move forward.

Let us look into the code snippet.

`class MaxWaterHolder:    def maxArea(self, height: List[int]) -> int:        left = 0        right  = len(height)-1        max_water = 0        while(left < right):            max_water = max(max_water, min(height[left], height[right])*(right-left))            if height[left] < height[right]:                left += 1            else:                right -= 1        return max_water`

Complexity analysis.

Time Complexity

We are traversing the list just once. Hence the time complexity is O(N).

Space Complexity.

We are not using any extra data structure to store anything. Hence the space complexity is O(1).

I would love to hear your feedback about my posts. Do let me know if you have any comments or feedback.

## More from Annamariya Tharayil

Software Engineer. Find me @ www.linkedin.com/in/annamariya-jt