Find area of container with most water in Python
In this tutorial, we will solve a problem in which we will find the area of the container which contains maximum water i.e, finding the maximum area of the container in Python.
Problem Statement: most water problem in Python
Given a list that has non-negative elements, in which each represents a point of the coordinate as (i, Ai).
There are n vertical lines that are drawn such that the two endpoints of the ith line are (i,0) and (i, Ai), where Ai is the element of the list at the ith position and i is the position.
In all these lines, two lines with an x-axis form a container that has a maximum area(contains most water). Find the maximum area.
- Since we are using a 2D plane so we are taking area instead of volume. Taking area is quite easy in comparison to volume.
- We can’t slant the container.
5 and 4 are 2 distances apart. The size of the base of the container = 2 and the Height of the container is min(5,4).
Thatswhy, the maximum area of container in which most waters contains is (4*2) = 8.
One way to solve this problem is by using the Brute force technique, for each i find area with all j >= i till i<len(list).Store maximum area calculated by each i in the list and then take a maximum of that list.
Explanation for Brute force :
For i = 0,
Area between line i=0 and others i which is greater than equal to i=0 : min(1,1) * 0 = 0
min(1,5)*1 = 1
min(1,3)*2 = 2
min(1,4)*3 = 3
So maximum area for i=0 is 3.Store it in the list(LIST).And do the same things for all the elements of list(given). Lastly, take a maximum of list(LIST) in which we are storing maximum area for each i .
This is the Brute force technique that we can use to find our output. But it will take O(n^2) time complexity.
The explanation for Two – Pointer Concept:
I will use Two pointer concept to solve this problem and it will take O(n) time complexity and O(1) space. Using the two-pointer concept will be more efficient.
In Two pointer concept, I will use two pointers one will work from the front of the list and the other will work from the end of the list. Each time we will take min(l[i],l[j]) where i pointed to the element from the front side of the list and j will point to the element from the last side of the list.
After taking min(l[i],l[j]) we will find area using (j-i) as breadth and min(l[i],l[j]) as height.
And we will increment i if l[i] < min(l[i],l[j]) and we will decrement j if l[j] < min(m[i],l[j]).
In this way, we will iterate through the list and find the maximum area which is required.
So now the code for the given problem:
def conta(l): i=0 # one pointer n = len(l) j= n -1 area = 0 while(i<j): height = min(l[i],l[j]) area = max(area,(height*(j-i))) if(l[i] <= height): i = i+1 elif(l[j] <=height): j = j+1 print("Container's area which contain most water:",area) conta([1,5,3,4])
Container's area which contain most water: 8
Do comment if you like this content and comment suggestions regarding this tutorial if require.