Container With Most Water - Leetcode Solution

Container With Most Water is a classic two-pointer approach problem on LeetCode. The problem statement reads: 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 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.

The idea behind solving this problem is to use the two-pointer approach, where we use two pointers, left and right, to traverse the array from both ends. We will start with the widest container in the array, which is represented by the left and right pointers, and we will keep moving the pointers towards each other until they meet.

During the traversal, we calculate the area of the container bounded by the two pointers, which is given by the formula (min(a[left], a[right]) * (right - left)). We keep track of the maximum area encountered so far and return it as the final answer.

Here's the detailed solution to the Container With Most Water problem:

Algorithm:

1. Initialize two pointers, left = 0 and right = n-1, where n is the length of the input array.
2. Initialize a variable maxArea to 0, which will store the maximum area encountered so far.
3. While left < right: a. Calculate the area of the container bounded by the two pointers, which is given by the formula (min(a[left], a[right]) * (right - left)). b. If the calculated area is greater than maxArea, update maxArea to the calculated area. c. If a[left] < a[right], increment left by 1. d. Else, decrement right by 1.
4. Return maxArea as the final answer.

Let's understand the above algorithm through an example:

Input: [1,8,6,2,5,4,8,3,7] Output: 49

Step 1: Initialize two pointers, left = 0 and right = n-1, where n is the length of the input array.

Left pointer --> | 1,8,6,2,5,4,8,3,7 | Right pointer --> | 1,8,6,2,5,4,8,3,7 |

Step 2: Initialize a variable maxArea to 0, which will store the maximum area encountered so far.

maxArea = 0

Step 3: While left < right: a. Calculate the area of the container bounded by the two pointers, which is given by the formula (min(a[left], a[right]) * (right - left)).

At the beginning, left = 0, right = 8, and a[left] = 1, a[right] = 7
Area = min(a[left], a[right]) * (right - left) = min(1, 7) * (8 - 0) = 8
maxArea = max(maxArea, Area) = max(0, 8) = 8

While moving the pointers:

At left = 1, right = 8, and a[left] = 8, a[right] = 7
Area = min(a[left], a[right]) * (right - left) = min(8, 7) * (8 - 1) = 56
maxArea = max(maxArea, Area) = max(8, 56) = 56

At left = 1, right = 7, and a[left] = 8, a[right] = 3
Area = min(a[left], a[right]) * (right - left) = min(8, 3) * (7 - 1) = 24
maxArea = max(maxArea, Area) = max(56, 24) = 56

At left = 1, right = 6, and a[left] = 8, a[right] = 8
Area = min(a[left], a[right]) * (right - left) = min(8, 8) * (6 - 1) = 40
maxArea = max(maxArea, Area) = max(56, 40) = 56

At left = 1, right = 5, and a[left] = 8, a[right] = 4
Area = min(a[left], a[right]) * (right - left) = min(8, 4) * (5 - 1) = 32
maxArea = max(maxArea, Area) = max(56, 32) = 56

At left = 1, right = 4, and a[left] = 8, a[right] = 5
Area = min(a[left], a[right]) * (right - left) = min(8, 5) * (4 - 1) = 12
maxArea = max(maxArea, Area) = max(56, 12) = 56

At left = 2, right = 4, and a[left] = 6, a[right] = 5
Area = min(a[left], a[right]) * (right - left) = min(6, 5) * (4 - 2) = 10
maxArea = max(maxArea, Area) = max(56, 10) = 56

At left = 2, right = 3, and a[left] = 6, a[right] = 2
Area = min(a[left], a[right]) * (right - left) = min(6, 2) * (3 - 2) = 2
maxArea = max(maxArea, Area) = max(56, 2) = 56

At left = 3, right = 3, and a[left] = 2, a[right] = 2
Area = min(a[left], a[right]) * (right - left) = min(2, 2) * (3 - 3) = 0
maxArea = max(maxArea, Area) = max(56, 0) = 56

At left = 4, right = 3, and a[left] = 5, a[right] = 2
Area = min(a[left], a[right]) * (right - left) = min(5, 2) * (2 - 4) = 0
maxArea = max(maxArea, Area) = max(56, 0) = 56

At left = 5, right = 3, and a[left] = 4, a[right] = 2
Area = min(a[left], a[right]) * (right - left) = min(4, 2) * (2 - 5) = 0
maxArea = max(maxArea, Area) = max(56, 0) = 56

At left = 6, right = 3, and a[left] = 8, a[right] = 2
Area = min(a[left], a[right]) * (right - left) = min(8, 2) * (2 - 6) = 0
maxArea = max(maxArea, Area) = max(56, 0) = 56

At left = 7, right = 3, and a[left] = 3, a[right] = 2
Area = min(a[left], a[right]) * (right - left) = min(3, 2) * (2 - 7) = 0
maxArea = max(maxArea, Area) = max(56, 0) = 56

At left = 8, right = 3, and a[left] = 7, a[right] = 2
Area = min(a[left], a[right]) * (right - left) = min(7, 2) * (2 - 8) = 0
maxArea = max(maxArea, Area) = max(56, 0) = 56

The pointers meet at left = right = 3, and the traversal ends.

Step 4: Return maxArea as the final answer.

Therefore, the maximum area of the container is 56.

Time Complexity: The time complexity of the above algorithm is O(n), where n is the length of the input array.

Space Complexity: The space complexity of the above algorithm is O(1), as we are not using any extra space.

Thus, we have successfully solved the Container With Most Water problem on LeetCode using the two-pointer approach.

1