11. Container With Most Water

MediumGreedyArrayTwo Pointers
Leetcode Link

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.

Learn more about Greedy and Two Pointers patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

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

1class Solution:
2    def maxArea(self, height: List[int]) -> int:
3        # Initialize two pointers, one at the beginning and one at the end of the height array
4        left, right = 0, len(height) - 1
5        # Initialize maximum area to 0
6        max_area = 0
7      
8        # Use a while loop to iterate until the two pointers meet
9        while left < right:
10            # Calculate the area formed between the two pointers
11            current_area = (right - left) * min(height[left], height[right])
12            # Update the maximum area if current_area is larger
13            max_area = max(max_area, current_area)
14          
15            # Move the pointer that points to the shorter line inward,
16            # since this might lead to a greater area
17            if height[left] < height[right]:
18                left += 1
19            else:
20                right -= 1
21      
22        # Return the maximum area found
23        return max_area
24```
25
26Please note that the type hint `List[int]` requires importing `List` from the `typing` module in Python 3.5+. If you're using Python 3.9+ it's also possible to use built-in list type hints directly like `list[int]`. If you want to include the necessary import, here's how you would do that:
27
28```python
29from typing import List  # This line is needed for the type hint (Python 3.5 - 3.8)
30
31class Solution:
32    # ... rest of the code remains the same
33
1class Solution {
2  
3    // Method to find the maximum area formed between the vertical lines
4    public int maxArea(int[] height) {
5        // Initialize two pointers at the beginning and end of the array
6        int left = 0; 
7        int right = height.length - 1;
8        // Variable to keep track of the maximum area
9        int maxArea = 0;
10      
11        // Iterate until the two pointers meet
12        while (left < right) {
13            // Calculate the area with the shorter line as the height and the distance between the lines as the width
14            int currentArea = Math.min(height[left], height[right]) * (right - left);
15            // Update the maximum area if the current area is larger
16            maxArea = Math.max(maxArea, currentArea);
17          
18            // Move the pointer that points to the shorter line towards the center
19            if (height[left] < height[right]) {
20                left++;
21            } else {
22                right--;
23            }
24        }
25      
26        // Return the maximum area found
27        return maxArea;
28    }
29}
30
1#include <vector>
2#include <algorithm> // Include algorithm for std::min and std::max
3
4class Solution {
5public:
6    int maxArea(vector<int>& heights) {
7        int left = 0; // Starting from the leftmost index
8        int right = heights.size() - 1; // Starting from the rightmost index
9        int maxArea = 0; // Initialize the maximum area to 0
10      
11        // Continue looping until the left and right pointers meet
12        while (left < right) {
13            // Calculate the current area with the minimum of the two heights
14            int currentArea = std::min(heights[left], heights[right]) * (right - left);
15            // Update the maximum area if the current area is larger
16            maxArea = std::max(maxArea, currentArea);
17          
18            // Move the pointers inward. If left height is less than right height
19            // then we move the left pointer to right hoping to find a greater height
20            if (heights[left] < heights[right]) {
21                ++left;
22            } else { // Otherwise, move the right pointer to the left
23                --right;
24            }
25        }
26      
27        return maxArea; // Return the maximum area found
28    }
29};
30
1function maxArea(height: number[]): number {
2    // Initialize two pointers, one at the start and one at the end of the array
3    let leftIndex = 0;
4    let rightIndex = height.length - 1;
5    // Initialize the variable to store the maximum area
6    let maxArea = 0;
7
8    // Iterate until the two pointers meet
9    while (leftIndex < rightIndex) {
10        // Calculate the area with the current pair of lines
11        const currentArea = Math.min(height[leftIndex], height[rightIndex]) * (rightIndex - leftIndex);
12        // Update maxArea if the current area is larger
13        maxArea = Math.max(maxArea, currentArea);
14
15        // Move the pointer that's at the shorter line inwards
16        // If the left line is shorter than the right line
17        if (height[leftIndex] < height[rightIndex]) {
18            ++leftIndex; // Move the left pointer to the right
19        } else {
20            --rightIndex; // Move the right pointer to the left
21        }
22    }
23
24    // Return the maximum area found
25    return maxArea;
26}
27
Not Sure What to Study? Take the 2-min Quiz：

Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?

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).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

In a binary min heap, the maximum element can be found in:

Recommended Readings

Greedy Introduction

Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

Tech Interview Pattern | Two Pointers Introduction

Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers iframe width 560 height 315 src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe Two pointers is a common interview technique

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫