Container With Most Water

Updated on 08 May, 2025
Container With Most Water header image

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

  • C++
  • Java
  • C
  • JavaScript
  • Python
cpp
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;
    }
};

The given C++ code aims to solve the problem of finding the maximum amount of water that can be trapped between two vertical lines, which represent the width apart and height dimensions given as an input in the form of a vector. The solution utilizes a two-pointer approach to efficiently determine the maximum water container formed.

  • The function largestWaterContainer takes a vector bars as an argument, representing the heights of the bars.
  • Variables maxWater, i, and j are initialized. maxWater is to store the maximum volume of water found, i is set to the start of the vector, and j to the end.
  • A while loop is used to process elements between i and j:
    • Calculate the distance between i and j.
    • maxWater is updated to the higher value between its current value and the water contained between bars i and j, which is the product of the distance and the minimum height of the two bars.
    • Depending on the relative heights of the bars at i and j, increment i if bars[i] is smaller or equal, else decrement j.
  • The loop iterates until i and j meet, ensuring each potential container is considered.
  • The function returns maxWater which holds the volume of the largest container of water.

This technique ensures a solution that is both time-efficient and space-efficient, bypassing the need for a brute-force approach which would have considerably higher time complexity.

java
public class Solution {
    public int maximumWater(int[] bars) {
        int maxWater = 0;
        int start = 0;
        int end = bars.length - 1;
        while (start < end) {
            int distance = end - start;
            maxWater = Math.max(
                maxWater,
                Math.min(bars[start], bars[end]) * distance
            );
            if (bars[start] <= bars[end]) {
                start++;
            } else {
                end--;
            }
        }
        return maxWater;
    }
}

The solution in Java aims to solve the "Container With Most Water" problem, which involves finding two lines (represented by an array of integers where each integer denotes the height of a line on a chart) that together with the x-axis forms a container that would hold the maximum amount of water.

In the provided solution:

  • Initialize maxWater to 0 to store the maximum amount of water the container can hold.
  • Use two pointers, start and end, initialized at the beginning and at the end of the array respectively. These pointers help in examining potential containers by moving towards each other until they meet.
  • Utilize a while loop to examine the area between the bars at start and end pointers. Calculate the distance between these two pointers, which acts as the width of the container.
  • The height of the container is determined by the smaller of the two bars (bars[start] and bars[end]) because the lower bar will be the limiting factor in the amount of water the container can hold.
  • Calculate the potential water containment using the formula (minimum height) * distance and update maxWater if the current area is larger.
  • Decide which pointer to move: move the start pointer right if the bar at start is shorter or equal to the bar at end (as possibly a taller bar towards the center might help contain more water), otherwise move the end pointer left.
  • Continue this process until the two pointers meet, and at the end, maxWater holds the maximum amount of water that can be trapped.

This approach efficiently determines the maximum water the container can hold by scanning the array only once with a time complexity of O(n), making it well-suited for larger arrays. This solution leverages the two-pointer technique to reduce unnecessary computations and provides a direct path to the solution.

c
int maximum(int x, int y) { return x > y ? x : y; }

int minimum(int x, int y) { return x < y ? x : y; }

int calculateMaxArea(int* heights, int size) {
    int area = 0;
    int start = 0;
    int end = size - 1;

    while (start < end) {
        int distance = end - start;
        area = maximum(area, minimum(heights[start], heights[end]) * distance);
        if (heights[start] <= heights[end]) {
            start++;
        } else {
            end--;
        }
    }
    return area;
}

The provided C program is designed to solve the "Container With Most Water" problem. This algorithm determines the maximum area of water that can be contained between two vertical lines represented by their heights.

The code defines three functions:

  • maximum(int x, int y): Returns the larger of two integers.
  • minimum(int x, int y): Returns the smaller of two integers.
  • calculateMaxArea(int* heights, int size): This is where the main logic is implemented to find the maximum area:

Follow these steps within calculateMaxArea:

  1. Initialize area to 0 to keep track of the largest area found.
  2. Use two pointers start and end to represent the indices of the line at the beginning and the end of the array, initializing start to 0 and end to size - 1.
  3. While start is less than end:
    • Calculate the distance between the two pointers.
    • Compute the area formed between the lines at indices start and end, which is the product of the smaller height and the distance. Use the maximum function to update area if a larger area is found.
    • To potentially find a larger area, decide whether to move the start pointer or the end pointer. If the height at start is less than or equal to the height at end, increment the start pointer; otherwise, decrement the end pointer.
  4. Return area as the maximum water area that can be trapped.

This algorithm leverages a two-pointer technique, optimizing the process by narrowing the search space based on the relative heights of the lines. This solution is efficient with a time complexity of O(n), where n is the number of elements in the heights array.

js
var computeMaxArea = function (heights) {
    let largestArea = 0;
    let start = 0;
    let end = heights.length - 1;

    while (start < end) {
        let width = end - start;
        largestArea = Math.max(
            largestArea,
            Math.min(heights[start], heights[end]) * width,
        );
        if (heights[start] <= heights[end]) {
            start++;
        } else {
            end--;
        }
    }
    return largestArea;
};

The solution to the problem of finding the container that can hold the most water is implemented in JavaScript. Essentially, it uses a two-pointer approach to determine the maximum area between height lines on a graph.

  • Start by initializing two pointers, one at the beginning (start) and one at the end (end) of the height array.
  • Initialize a variable largestArea to keep track of the maximum area found.
  • Use a while loop to iterate as long as start is less than end. Calculate the width as the difference between end and start.
  • Update largestArea with the maximum of its current value or the area calculated using the shorter line (Math.min(heights[start], heights[end])) multiplied by the width.
  • Depending on which side is shorter, move the corresponding pointer inward (start++ if the left side is shorter, otherwise end--).
  • Return largestArea once the loop exits. This value represents the maximum water that can be trapped between the lines.

The implementation efficiently calculates the container with the most water using linear time complexity, i.e., (O(n)), thanks to the two-pointer technique that narrows down the possible solutions without the need for nested iterations.

python
class Solution:
    def calculateMaxWater(self, bars: List[int]) -> int:
        max_water = 0
        start = 0
        end = len(bars) - 1

        while start < end:
            distance = end - start
            max_water = max(max_water, min(bars[start], bars[end]) * distance)
            if bars[start] <= bars[end]:
                start += 1
            else:
                end -= 1

        return max_water

The provided solution is a Python implementation to solve the problem of finding the maximum amount of water that can be contained between two bars of different or equal heights. The solution employs the two-pointer technique effectively. Here's a breakdown of how the solution works:

  • Initialize max_water to track the maximum amount of water contained, and two pointers, start and end, pointing at the beginning and the end of the bars list respectively.
  • Use a while loop to continue the procedure as long as start is less than end.
  • For each iteration, compute the distance between the start and end pointers. Calculate tentative water containment by computing the area formed between the bars at the start and end pointers, which is given by the minimum height of the two bars multiplied by the distance between them. Update max_water if this area is greater than the current max_water.
  • To move the pointers efficiently, compare the heights at start and end. Increment the start pointer if the bar at start is less than or equal to the bar at end, otherwise decrement the end pointer. This ensures that the potential for maximizing the water containment is checked by narrowing down to the higher bars.
  • Finally, return the value of max_water which will be the maximum water that can be contained between any two bars.

This solution is efficient with a time complexity of O(n) where n is the number of bars, due to the single Pass through the list using the two-pointer approach.

Comments

No comments yet.