Leetcode 11: Container With Most Water

Category: Medium

Problem

Given n non-negative integers a₁, a₂, ..., a_n, where each represents a point at coordinate (i, a_i). n vertical lines are drawn such that the two endpoints of the line i is at (i, a_i) 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.

https://leetcode.com/problems/container-with-most-water/

Examples

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: 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.

Input: height = [1,8,6,2,5,4,8,3,7]

Output: 49

Explanation: 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

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

Example 3:

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

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

Example 4:

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

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

Constraints

n = height.length
2 <= n <= 3 * 10⁴
0 <= height[i] <= 3 * 10⁴

Solution Approach

In this problem, we have to find the container, which is made up of the vertical lines, which will hold most water or in short we have to find the two set of vertical lines which will contain the most surface area. The surface area can be calculated by the distance between the two vertical lines and multiplied by the value of the shortest among those two lines, therefore containing the most water.

The problem seems easy with brute force but let’s try a different more complex but more computation friendly approach. This approach is called the two pointer approach in which we will start a pointer from both the ends of the array and keep on decreasing one part depending on some condition. If the two pointers cross each other or if they meet then we will stop the computation. This will save the complexity and the worst complexity will be O(n) where n is the length of the array.

Coming to the solution now we first start with two pointers one at the start of the array and one at the end of it the pointer which is initially pointing to the start of the array will move from left to right and the one which initially points at the end of the array will move from right to left. With the initial pointers we find the volume with formula Volume = (x2 - x1) * min(y2, y1).

We will find the volume with each pointer movement and will update the largest volume if we find one. Now we loop through the entire array and we have to move the pointer whose length is shorter of the two. We do this till the two pointers overlap and return the maximum volume.

Solution code

class Solution {
  public int maxArea(int[] height) {
    int maxArea = 0;
    int left = 0, right = height.length - 1;
    while (left < right) {
      maxArea = Math.max(maxArea, Math.min(height[left], height[right]) * (right - left));
      if (height[left] > height[right]) right--;
      else left++;
    }
    return maxArea;
  }
}

class Solution {

public int maxArea(int[] height) {

int maxArea = 0;

int left = 0, right = height.length - 1;

while (left < right) {

maxArea = Math.max(maxArea, Math.min(height[left], height[right]) * (right - left));

if (height[left] > height[right]) right--;

else left++;

}

return maxArea;

}

For more Leetcode explained solutions visit Leetcode Solutions.

If you like capture the flag challenges visit here.

For Computer Science Quotes visit here and for more computer science-related topic visit my blog on Computer Science.

Check out my socials below in the footer. Feel free to ask any doubts in the comment section or contact me via Contact page I will surely respond. Happy Leetcoding 🙂