Container With Most Water

Problem Statement

In this problem, you are presented with an array of integers named height which represents the heights of vertical lines, drawn on a coordinate system where the x-axis serves as the base. The lines span from the coordinates (i, 0) to (i, height[i]) where i is the index of the current element in the array. The task is to determine the maximum volume of water that can be held between any two lines, forming a vertical-sided container. This is akin to finding two indices i and j such that the area between these two lines (with the x-axis as the third boundary) is maximized. The container's sides are made up by the height of the lines at these two indices, and its width is the horizontal distance between them. Note that the container cannot be slanted; it must have vertical sides and be perpendicular to the horizontal axis.

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.

Example 2

Input:

height = [1,1]

Output:

1

Constraints

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

Approach and Intuition

The primary goal is to find the maximum area formed by any two lines in the array where the area calculation depends on the formula: Area = min(height[i], height[j]) * (j - i). This formula arises from:

• The minimum of two heights because the water level can only rise as high as the shorter line among the pair of lines chosen.
• The distance between the two lines gives the width of the container.

Here's the intuitive approach based on the examples and constraints:

1. Two-pointer approach:
   • Start with two pointers, one at the beginning (left) and the other at the end (right) of the array.
   • Calculate the area with height[left] and height[right] as the heights of the container and the difference of indices as the width.
   • Keep a record of the maximum area found so far.
   • Adjust the pointers:
     • Move the pointer pointing to the shorter line towards the other, in hopes of finding a taller line that could potentially increase the area.
     • This is because if we move the pointer at the taller line, the area is limited by the shorter line, and by moving the shorter line's pointer, there's potential to increase the minimum height and thus the area.
     • Continue this until the two pointers meet.

Example walkthrough:

• For the array [1,8,6,2,5,4,8,3,7]:
  • Starting with left = 0 and right = 8, the minimum height is 1 (from height[0]), and width is 8. Area calculation gives 1 * 8 = 8.
  • Increment left (since height[0] < height[8]) to potentially find a taller line.
  • Continue this process adjusting pointers and calculating areas.
  • The maximum area found would be 49, occurring between the lines at indices 1 and 8.

With these considerations, the application of a two-pointer technique is both intuitive and efficient given the constraints, allowing us to solve the problem in linear time O(n).

Solutions

class Solution {
public:
    int largestWaterContainer(vector<int>& bars) {
        int maxWater = 0;
        int i = 0;
        int j = bars.size() - 1;
    
        while (i < j) {
            int distance = j - i;
            maxWater = max(maxWater, min(bars[i], bars[j]) * distance);
            if (bars[i] <= bars[j]) {
                i++;
            } else {
                j--;
            }
        }
        return maxWater;
    }
};