Problem Explanation

In this problem, we have all non-negative integers given in an array. Each element represents a vertical wall at the corresponding index on the x-axis that extends up to a height that equals the value of that element.

We need to find two vertical walls (elements) from this array that, when combined with the x-axis, forms a container with maximum capacity. The size of the container, or rather the amount of water it can hold, is dependent on the distance between the two walls on the x-axis and the height of the shorter wall.

For example, given the array [1,8,6,2,5,4,8,3,7], the maximum capacity is 49. This happens when we select the second wall (height 8, index 1) and the last wall (height 7, index 8). The shorter wall is 7, and the distance between them is 7 (8-1), thus the maximum area is 7x7 = 49.

Approach

The solution uses the Two Pointers technique. Initially, we consider the container formed by the farthest two lines and keep shrinking our container inwards in order to maximize the area.

A key insight for this solution is that the area filled is always limited by the height of the shorter line. So, we iterate through the array, each time calculating a new potential maximum area and update our maximum area if the new area is larger.

During iteration, we move the pointer of the shorter wall inwards because there is a chance to find a wall that is longer and will thus form a larger container. If we move the pointer of the larger wall, we will not get a larger container, as the shorter wall will always limit the size of the container.

Python Solution

1
2python
3class Solution:
4    def maxArea(self, height):
5        l, r = 0, len(height) - 1
6        max_area = 0
7        
8        while l < r:
9            h = min(height[l], height[r])
10            w = r - l
11            area = h * w
12            max_area = max(max_area, area)
13            
14            if height[l] < height[r]:
15                l += 1
16            else:
17                r -= 1
18        return max_area

Java Solution

1
2Java
3public class Solution {
4    public int maxArea(int[] height) {
5        int l = 0;
6        int r = height.length - 1;
7        int maxArea = 0;
8
9        while (l < r) {
10            int h = Math.min(height[l], height[r]);
11            int w = r - l;
12            int area = h * w;
13            maxArea = Math.max(maxArea, area);
14
15            if (height[l] < height[r]) {
16                l++;
17            } else {
18                r--;
19            }
20        }
21        return maxArea;
22    }
23}

JavaScript Solution

1
2javascript
3class Solution{
4    maxArea(height) {
5        let l = 0, r = height.length - 1;
6        let maxArea = 0;
7
8        while(l < r){
9            let h = Math.min(height[l], height[r]);
10            let w = r - l;
11            let area = h * w;
12            maxArea = Math.max(maxArea,area);
13
14            if(height[l] < height[r]){
15                l++;
16            }
17            else {
18                r--;
19            }
20        }
21        return maxArea;
22     }
23}

C++ Solution

1
2C++
3class Solution {
4public:
5    int maxArea(vector<int>& height) {
6        int l = 0, r = height.size() - 1;
7        int maxArea = 0;
8
9        while (l < r) {
10            int h = min(height[l],height[r]);
11            int w = r - l;
12            int area = h * w;
13            maxArea = max(maxArea, area);
14
15            if (height[l] < height[r])
16                l++;
17            else
18                r--;
19        }
20        return maxArea;
21    }
22};

C# Solution

1
2Csharp
3public class Solution {
4    public int MaxArea(int[] height) {
5        int l = 0;
6        int r = height.Length - 1;
7        int maxArea = 0;
8
9        while (l < r) {
10            int h = Math.Min(height[l], height[r]);
11            int w = r - l;
12            int area = h * w;
13            maxArea = Math.Max(maxArea, area);
14
15            if (height[l] < height[r]) {
16                l++;
17            } else {
18                r--;
19            }
20        }
21        return maxArea;
22    }
23}

Notes

All the solutions have a linear time complexity of O(n), as we visit each element in the height array only once.Overall, the problem of calculating the maximum area of a container filled with water is quite easy to understand, but might not have an obvious solution. The key lies in the two pointers technique and understanding the nature of the problem.

Initially, two pointers are placed at the beginning and end of the array representing the position of the walls. In each iteration, the pointers check the area between the two walls and compare it with the maximum area calculated so far.

The clever part of this approach is that after each check, the pointer pointing to the shorter wall moves one step towards the other pointer. Since the area is limited by the height of the shorter wall, moving the pointer at the taller wall inwards will not lead to a larger area. This is because the move would result in a reduction in width without an increase in height.

In the worst-case scenario, all elements of the array will be traversed once, that is why the time complexity is O(n), where n represents the length of the input array. This makes this approach very efficient. It is also in-place as it does not require extra space which makes it a memory-wise efficient solution as well.

In conclusion, the key takeaway from this problem would be understanding the nature of the container filling process and how moving the pointers towards each other can result in accurate and efficient solutions. This approach could also be applied to other similar problems where you need to find optimal pairings in an array.