11. Container With Most Water

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

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

Problem Description

You are presented with an integer array called height which represents the heights of vertical lines placed at positions indexed from 1 to n (0-indexed in the array). Imagine that each height[i] is linked to a line on a chart that extends upward from the x-axis to a point (i, height[i]). Your task is to find two lines that, along with the x-axis, enclose the greatest possible area, which represents the maximum water that can be trapped between them without allowing any spillage over the sides of the lines (the container cannot be slanted). The goal is to calculate and return this maximum trapped water area.

Intuition

To solve this problem efficiently, we use a two-pointer technique. We place one pointer at the beginning of the array and the other at the end, and these pointers represent the potential container boundaries. At each step, the trapped water is determined by the distance between the pointers (which is the container’s width) and the height of the smaller line (since the water level can’t be higher than the smaller of the two boundaries). This is the area that could potentially be the maximum.

To maximize the area, after calculating the trapped water at each step and comparing it to the maximum we’ve seen so far, we move the pointer at the shorter line towards the other pointer. This is because keeping the pointer at the taller line stationary and moving the shorter one might lead us to find a taller line and thus a larger area. There’s no advantage in moving the taller pointer first, as it would only reduce the potential width without guaranteeing a taller line to increase height. We repeat this process of calculating, updating the maximum water area, and moving the shorter line pointer towards the other pointer until the two pointers meet, at which point we’ve considered every possible container and the maximum stored water has been found.

By approaching this problem with each step optimized to either maintain or improve the potential maximum area, we are able to arrive at the solution efficiently, resulting in an algorithm that runs in linear time relative to the number of lines.

Solution Approach

The implementation of the solution follows the two-pointer approach. Here’s a step-by-step guide to how the solution works:

  1. Initialize two pointers: i is set to the start of the array (0), and j is set to the end of the array (len(height) - 1).
  2. Initialize a variable ans to keep track of the maximum area discovered so far. Initially, ans is set to 0.
  3. Enter a loop that continues as long as i is less than j. This loop allows us to explore all possible combinations of lines from i to j to maximize the area.
  4. Inside the loop, calculate the area trapped between the lines at pointers i and j using the formula: area = (j - i) * min(height[i], height[j]). This calculates the width of the container (j - i) and multiplies it by the height, which is the smaller of the two heights at height[i] and height[j].
  5. Update ans with the maximum of its current value and the calculated area. ans = max(ans, area) ensures that ans holds the highest value of trapped water area at each step.
  6. Determine which pointer to move. We need to move the pointer corresponding to the shorter line since this is the limiting factor for the height of the trapped water. We do this using a conditional statement:
    • If height[i] < height[j], then we increment i (i += 1) to potentially find a taller line.
    • Else, decrement j (j -= 1) for the same reason from the other end.
  7. Continue looping until the pointers meet. At this point, ans would have the maximum area that can be trapped between any two lines.

This solution uses a greedy approach, and its efficiency stems from the fact that at each stage, the move made is the best possible move to increase or at least maintain the potential of the maximum area. By incrementally adjusting the width and height of the considered container, it efficiently narrows down to the optimal solution.

The algorithm has a linear-time complexity, O(n), as each element is visited at most once, and there’s a constant amount of work done within the loop.

Example Walkthrough

Let’s illustrate the solution approach using a small example.

Consider the integer array height = [1, 8, 6, 2, 5, 4, 8, 3, 7].

  1. We start with two pointers: i at the start (0), representing the first line, and j at the end (8), representing the last line. Thus, i points to height[0] which is 1, and j points to height[8] which is 7.
  2. We set ans = 0, as we have not calculated any area yet.
  3. Now we start our loop where i < j. Since 0 < 8, we enter the loop.
  4. We calculate the area between lines at pointers i and j. The width is j - i which is 8 - 0 = 8, and the height is the smaller of two heights at height[i] and height[j], so min(1, 7) = 1. Thus, the area is 8 * 1 = 8.
  5. We update ans to be the maximum of its current value and the calculated area. So, ans = max(0, 8) = 8.
  6. Since height[i] is less than height[j], we move the i pointer to the right to potentially find a taller line. Now i becomes 1.
  7. Our two pointers now are at i = 1 and j = 8. We will continue this process until i and j meet.
  8. Repeat steps 4-6:
    • New area at pointers i = 1 and j = 8: area = (8 - 1) * min(8, 7) = 7 * 7 = 49.
    • Update ans to be max(8, 49) = 49.
    • Since height[1] is greater than height[8], we move j to the left (now j is 7).
  9. Continue iterations:
    • New area at pointers i = 1 and j = 7: area = (7 - 1) * min(8, 3) = 6 * 3 = 18.
    • ans remains 49 since 49 > 18.
    • height[1] is greater than height[7], so we move j to the left (now j is 6).
  10. The process continues in this manner, always moving the pointer at the shorter height until i and j are equal.

At the end of these iterations, ans holds the maximum area that can be trapped, which in this example, is 49. This is the largest amount of water that can be trapped between two lines without spilling.

Solution Implementation

class Solution {
public:
    int maxArea(vector<int>& height) {
        int maxArea = 0;  // Variable to store the maximum area found
        int left = 0;  // Left pointer, starting at the beginning of the array
        int right = height.size() - 1;  // Right pointer, starting at the end of the array

        // Loop until the left pointer meets the right pointer
        while (left < right) {
            // Calculate the area and update maxArea if a larger area is found
            maxArea = max(maxArea, (right - left) * min(height[left], height[right]));

            // Move the pointer pointing to the smaller height towards the center
            if (height[left] < height[right]) {
                left++;  // Move left pointer to the right
            } else {
                right--;  // Move right pointer to the left
            }
        }

        return maxArea;  // Return the maximum area found
    }
};
Copied!

class Solution {
    public int maxArea(int[] height) {
        int maxArea = 0;  // Variable to store the maximum area found
        int left = 0;  // Left pointer, starting at the beginning of the array
        int right = height.length - 1;  // Right pointer, starting at the end of the array

        // Loop until the left pointer meets the right pointer
        while (left < right) {
            // Calculate the area and update maxArea if a larger area is found
            maxArea = Math.max(maxArea, (right - left) * Math.min(height[left], height[right]));

            // Move the pointer pointing to the smaller height towards the center
            if (height[left] < height[right]) {
                left++;  // Move left pointer to the right
            } else {
                right--;  // Move right pointer to the left
            }
        }

        return maxArea;  // Return the maximum area found
    }
}
Copied!
class Solution:
 def maxArea(self, height: List[int]) -> int:
     max_area = 0  # Variable to store the maximum area found
     left = 0  # Left pointer, starting at the beginning of the array
     right = len(height) - 1  # Right pointer, starting at the end of the array
     # Loop until the left pointer meets the right pointer
     while left < right:
         # Calculate the area and update max_area if a larger area is found
         max_area = max(max_area, (right - left) * min(height[left], height[right]))
         # Move the pointer pointing to the smaller height towards the center
         if height[left] < height[right]:
             left += 1  # Move left pointer to the right
         else:
             right -= 1  # Move right pointer to the left
     
     return max_area  # Return the maximum area found
Copied!
int maxArea(int* height, int heightSize) {
    int left = 0;                // Left pointer starting from the leftmost edge
    int right = heightSize - 1;  // Right pointer starting from the rightmost edge
    int maxWater = 0;            // Initialize the maximum water capacity

    while (left < right) {
        // Calculate the width of the container
        int width = right - left;

        // Calculate the height of the container (the minimum height between the two lines)
        int h = height[left] < height[right] ? height[left] : height[right];

        // Calculate the water capacity of the current container
        int water = width * h;

        // Update the maximum water capacity if the current container holds more water
        if (water > maxWater) {
            maxWater = water;
        }

        // Move the pointers towards each other
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }

    return maxWater;
}
Copied!
public class Solution {
    public int MaxArea(int[] height) {
        int res = 0;  // Variable to store the maximum area found

        int left = 0;  // Left pointer, starting at the beginning of the array
        int right = height.Length - 1;  // Right pointer, starting at the end of the array

        // Loop until the left pointer meets the right pointer
        while(left < right) {
            // Calculate the area and update res if a larger area is found
            int area = (right - left) * Math.Min(height[left], height[right]);
            res = Math.Max(res, area);

            // Move the pointer pointing to the smaller height towards the center
            if(height[left] < height[right]) left++;  // Move left pointer to the right
            else right--;  // Move right pointer to the left
        }

        return res;  // Return the maximum area found
    }
}
Copied!
var maxArea = function(height) {
    let left = 0;            // Left pointer starting from the leftmost edge
    let right = height.length - 1; // Right pointer starting from the rightmost edge
    let maxWater = 0;        // Initialize the maximum water capacity
    
    while (left < right) {
        // Calculate the width of the container
        let width = right - left;
        
        // Calculate the height of the container (the minimum height between the two lines)
        let h = Math.min(height[left], height[right]);
        
        // Calculate the water capacity of the current container
        let water = width * h;
        
        // Update the maximum water capacity if the current container holds more water
        maxWater = Math.max(maxWater, water);
        
        // Move the pointers towards each other
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    
    return maxWater;
};
Copied!
function maxArea(height: number[]): number {
  // we'll use the 2 pointer approach to solve the problem
  // as we need to the maximum amount of water the container
  // can store, we'll have the pointers from 0 till n-1
  let low = 0;
  let high = height.length - 1;
  let ans = 0;

  while (low <= high) {
    // we'll calcuate the length and breadth of the container
    // and then we'll keep track of the highest value

    // as the note in the problem says that we cannot slant
    // the container, so for length we need to take the lowest
    // value else the line will not be parallel to the x-axis
    // and we'll have a slant
    const length = Math.min(height[low], height[high]);

    // for breadth we need to find the distance between the 2 pointers
    const breadth = high - low;
    const area = length * breadth;

    // store the highest value
    ans = Math.max(ans, area);

    // now we need to move either the i pointer or j pointer
    // as we require the container to be max, we need to move
    // the smallest value between low and high pointer
    if (height[low] < height[high]) low++;
    else high--;
  }
  return ans;
};
Copied!
class Solution {
    public function maxArea(array $altura): int {
 
        // Paso #1
        $puntero1 = 0;
        $puntero2 = count($altura) - 1;
        $areaMaxima = 0;
 
        // Paso #2
        while ($puntero1 != $puntero2) {
 
            // Paso #3
            $anchura = $puntero2 - $puntero1;
 
            // Paso #4
            $areaActual = $anchura * min($altura[$puntero1], $altura[$puntero2]);
 
            // Paso #5
            if ($areaActual > $areaMaxima) {
                $areaMaxima = $areaActual;
            }
 
            // Paso #6
            if ($altura[$puntero1] <= $altura[$puntero2]) {
                $puntero1++;
            } else {
                $puntero2--;
            }
        }
 
        // Paso #7
        return $areaMaxima;
    }
}
Copied!

class Solution {
    func maxArea(_ height: [Int]) -> Int {
        var maxArea = Int.min  // Variable to store the maximum area found, initialized to the smallest possible value
        var low = 0  // Left pointer, starting at the beginning of the array
        var hight = height.count - 1  // Right pointer, starting at the end of the array

        // Loop until the left pointer meets the right pointer
        while low < hight {
            // Calculate the area between the two pointers and update maxArea if a larger area is found
            let area = min(height[low], height[hight]) * (hight - low)

            maxArea = max(area, maxArea)  // Update maxArea with the larger of the current area and maxArea

            // Move the pointer pointing to the smaller height towards the center
            if height[low] < height[hight] {
                low += 1  // Move low pointer to the right
            } else {
                hight -= 1  // Move hight pointer to the left
            }
        }

        return maxArea  // Return the maximum area found
    }
}
Copied!
import kotlin.math.max
import kotlin.math.min

class Solution {
    fun maxArea(height: IntArray): Int {
        var l = 0  // Left pointer, starting at the beginning of the array
        var r = height.size - 1  // Right pointer, starting at the end of the array
        var area = 0  // Variable to store the maximum area found

        // Loop until the left pointer meets the right pointer
        while (l != r) {
            // Calculate the area and update max area if a larger area is found
            area = max(area, min(height[l], height[r]) * (r - l))

            // Move the pointer pointing to the smaller height towards the center
            if (height[l] > height[r]) {
                r -= 1  // Move right pointer to the left
            } else {
                l += 1  // Move left pointer to the right
            }
        }

        return area  // Return the maximum area found
    }
}
Copied!
class Solution {
  int maxArea(List height) {

    int left = 0;  // Left pointer, starting at the beginning of the array
    int right = height.length - 1;  // Right pointer, starting at the end of the array

    int maxArea = 0;  // Variable to store the maximum area found

    // Loop until the left pointer meets the right pointer
    while (left < right) {

      int width = right - left;  // Calculate the width between the two pointers
      int ht = min(height[left], height[right]);  // Find the minimum height between the two pointers

      int area = width * ht;  // Calculate the area between the two pointers

      maxArea = max(maxArea, area);  // Update maxArea if the current area is larger

      // Move the pointer pointing to the smaller height towards the center
      (height[left] < height[right]) ? left++ : right--;  // Increment left if left height is smaller, otherwise decrement right
    }

    return maxArea;  // Return the maximum area found
  }
}
Copied!
func maxArea(height []int) int {
    var maxArea int  // Variable to store the maximum area found

    // Loop until the left pointer meets the right pointer
    for left, right := 0, len(height)-1; left < right; {
        var currArea int  // Variable to store the current area between the two pointers

        // Check which height is smaller and calculate the area
        if height[left] <= height[right] {
            currArea = (right-left) * height[left]  // Calculate the area using the left height
            left++  // Move the left pointer to the right
        } else {
            currArea = (right-left) * height[right]  // Calculate the area using the right height
            right--  // Move the right pointer to the left
        }

        // Update maxArea if the current area is larger
        if currArea > maxArea {
            maxArea = currArea
        }
    }

    return maxArea  // Return the maximum area found
}
Copied!

Time and Space Complexity

The given Python code implements a two-pointer technique to find the maximum area of water that can be contained between two lines, given an array of line heights.

Time Complexity

The function initializes two pointers at the start and end of the array respectively and iterates inwards until they meet, performing a constant number of operations for each pair of indices. Since the pointers cover each element at most once, the iteration is linear relative to the number of elements n in the height array.

Hence, the time complexity is O(n).

Space Complexity

The code uses a fixed number of integer variables (i, j, ans, and t) and does not allocate any additional memory that scales with the size of the input array.

Thus, the space complexity is O(1).

One thought on “11. Container With Most Water”

  1. Excellent read, I just passed this onto a colleague who was doing a little research on that. And he just bought me lunch because I found it for him smile Thus let me rephrase that: Thank you for lunch!

Leave a Reply

Your email address will not be published. Required fields are marked *