Container With Most Water — Python(Day 40)

Photo by Kaitlyn Baker on Unsplash

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:

Example 2:

Example 3:

Example 4:

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.

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.

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.

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

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store