Container with Most Water in Python

Imagine you are at a beach with a series of poles of different heights stuck in the sand. You want to collect as much rainwater as possible between two poles. The width of the container is the distance between the two poles, and the height is the shorter pole. This is similar to the container with most water problem in Python.

Problem statement

Given a list of non-negative integers heights, where each integer represents the height of a pole at that position, find two poles that together with the x-axis form a container that can hold the most water.

Example

1heights = [1, 8, 6, 2, 5, 4, 8, 3, 7]
2# Output: 49

Explanation: The most water is contained between the poles at indices 1 and 8, which forms a container with an area of (8−1)×min(8,7)=49.

How to solve

To solve the container with most water problem, we use a two-pointer technique:

• Set Two Pointers: One at the beginning (left) and one at the end (right) of the list.
• Calculate Area: Calculate the area between the two pointers.
• Move Pointers: Move the pointer that points to the shorter pole towards the other pointer to try and find a taller pole that can form a larger area.

Full code in Python

Here's the complete Python code to solve the container with most water problem:

1def maxArea(heights):
2    left, right = 0, len(heights) - 1
3    max_area = 0
4
5    while left < right:
6        width = right - left
7        current_area = width * min(heights[left], heights[right])
8        max_area = max(max_area, current_area)
9
10        if heights[left] < heights[right]:
11            left += 1
12        else:
13            right -= 1
14
15    return max_area
16
17# Example usage
18heights = [1, 8, 6, 2, 5, 4, 8, 3, 7]
19print("Container with most water: ", maxArea(heights))

Explanation of the code

• Set Pointers: Initialize left to the start and right to the end of the list.
• Calculate Areas: Use a loop to calculate the area between the two pointers. Update max_area if the current area is larger.
• Move Pointers: Move the pointer pointing to the shorter pole inward to find a potentially taller pole that can form a larger area.
• Return the Maximum Area: Once the pointers meet, return the maximum area found.

Time complexity

The time complexity of this solution is O(n), where n is the number of elements in the heights list. This is because we only make one pass through the list with the two pointers.