Container with Most Water
Problem Description
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.
Problem Explanation
The problem is about finding the maximum amount of water a container can hold using two lines from a given array.
You are given an array called height. Each number in the array represents the height of a vertical line at that position. To form a container, you pick any two lines from the array, and the x-axis (the horizontal line) acts as the base of the container.
The width of the container is the distance between the two lines (the difference in their positions in the array), and the height of the container is the shorter of the two lines.
Your task is to determine which two lines make the container that can hold the most water and return the amount of water it can hold.
“Slant the container”, what does this mean?
It means the container's sides (the two lines you choose) must remain vertical and parallel to the y-axis. You cannot tilt or angle the lines.
Examples:
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by an array [1,8,6,2,5,4,8,3,7]. In this case, the maximum area of water (blue section) the container can contain is 49.
Input: height = [1,1]
Output: 1
Explanation: The max area of water between the heights is 1.
Constraints:
- n == height.length
- 2 <= n <= 10⁵
- 0 <= height[i] <= 10⁴
Let’s try to simulate the problem step by step to build a clear understanding of how to approach it. We aim to find two lines in the array that form a container holding the maximum water.
For each pair of lines, the water it can hold depends on the shorter line’s height and the distance between the two lines. By visualizing how the container is formed and how the area changes based on different pairs of lines, we can develop a straightforward solution. After understanding this, we’ll explore ways to improve and make the solution more efficient.
Brute Force Approach
Intuition
Imagine you have an array of integers, each representing the height of a vertical line drawn along the x-axis. These lines are positioned one after another starting from position 1 to n. Your task is to find two vertical lines that, along with the x-axis, form a container that can hold the maximum amount of water. The challenge is determining which line pair will give you the largest container.
For example, if the array is [1,8,6,2,5,4,8,3,7], these heights represent vertical lines at positions 1 to 9 on the x-axis. You need to select two of these lines that maximize the area of the container they form. This container is defined by the two lines and the x-axis as its base. Now let’s make this clearer.
Understanding the Container?
To form a container, you choose two vertical lines from the array. The distance between these two lines (their positions on the x-axis) is the width of the container. The height of the container is determined by the shorter of the two selected lines because water cannot go above the shorter line.
For example, if you select lines at positions 2 and 8 with heights 8 and 3, the container's width is 8−2=6, and its height is the smaller of the two heights, which is 3. Therefore, the area of the container is width×height = 6×3 = 18.
The formula to calculate the area of the container formed by two lines at positions i and j is:
Area = (j - i) × min(height[i], height[j])
Here, i and j are the positions of the two lines, and height[i] and height[j] are their respective heights, here (j - i) is the width between the two vertical lines.
Why Use the Minimum Height?
The height of the container depends on the shorter line because water cannot go above the shorter line’s height. For instance, if one line is 7 units tall and the other is 4 units tall, the water level is restricted to 4 units, no matter how tall the other line is. This is why the height of the container is taken as the minimum of the two-line heights.
This concept ensures that the container is a rectangle, as its height is always limited by the shorter of the two lines. Understanding this is key to calculating the area accurately.
Now that we know how to calculate the area for any two lines, the next question is: How do we find the best pair of lines? The first idea that comes to mind is to calculate the area for all possible pairs of lines. You check every pair, calculate the area, and keep track of the maximum area encountered.
For example, if there are 9 lines in the array, you compare line 1 with lines 2 through 9, then line 2 with lines 3 through 9, and so on.
Dry-run
Input: [2, 5, 8, 4, 4, 5]
Output: 20
Explanation: This area is obtained by two integers situated at index 1 and 5, hence width is 5-1=4 and height is minimum of height[1] and height[5] = 5, giving a total area of 20. There is no other pair which results in a greater area than 20.
Initialization
- maxArea = 0 (stores the maximum area found so far).
- n = 6 (length of the height array).
Outer Loop (i-loop):
The outer loop iterates over i from 0 to n−1.
Step 1: i = 0
- Inner Loop (j-loop): Iterates j from 0 to 5.
- j=0:
- currArea = (0-0) * min(height[0], height[0]) = 0
- maxArea = max(0,0) = 0
- j=1:
- currArea = (1-0) * min(height[0], height[1]) = 1 * min(2, 5) = 2
- maxArea = max(0,2) = 2
- j=2:
- currArea = (2-0) * min(height[0], height[2]) = 2 * min(2, 8) = 4
- maxArea = max(2,4) = 4
- j=3:
- currArea= (3-0) * min(height[0], height[3]) = 3 * min(2, 4) = 6
- maxArea=max(4,6)=6
- j=4j:
- currArea = (4-0) * min(height[0], height[4]) = 4 * min(2, 4) = 8
- maxArea = max(6,8) = 8
- j=5:
- currArea = (5-0) * min(height[0], height[5]) = 5 * min(2, 5) = 10
- maxArea = max(8,10) = 10
Step 2: i = 1
- Inner Loop (j-loop): Iterates j from 1 to 5.
- j=1:
- currArea = (1-1) * min(height[1], height[1]) = 0
- maxArea = max(10,0) = 10
- j=2:
- currArea = (2-1) * min(height[1], height[2]) = 1 * min(5, 8) = 5
- maxArea = max(10,5) = 10
- j=3:
- currArea = (3-1) * min(height[1], height[3]) = 2 * min(5, 4) = 8
- maxArea = max(10,8) = 10
- j=4:
- currArea = (4-1) * min(height[1], height[4]) = 3 * min(5, 4) = 12
- maxArea = max(10,12) = 12
- j=5:
- currArea = (5-1) * min(height[1], height[5]) = 4 * min(5, 5) = 20
- maxArea = max(12,20) = 20
Step 3: i=2
- Inner Loop (j-loop): Iterates j from 2 to 5.
- j=2:
- currArea = (2-2) * min(height[2], height[2]) = 0
- maxArea = max(20,0) = 20
- j=3:
- currArea = (3-2) * min(height[2], height[3]) = 1 * min(8, 4) = 4
- maxArea = max(20,4) = 20
- j=4:
- currArea= (4-2) * min(height[2], height[4]) = 2 * min(8, 4) = 8
- maxArea = max(20,8) = 20
- j=5:
- currArea= (5-2) * min(height[2], height[5]) = 3 * min(8, 5) = 15
- maxArea = max(20,15) = 20
Step 4: i=3
- Inner Loop (j-loop): Iterates j from 3 to 5..
- j=3:
- currArea = (3-3) * min(height[3], height[3]) = 0
- maxArea = max(20,0) = 20
- j=4:
- currArea = (4-3) * min(height[3], height[4]) = 1 * min(4, 4) = 4
- maxArea = max(20,4) = 20
- j=5:
- currArea = (5-3) * min(height[3], height[5]) = 2 * min(4, 5) = 8
- maxArea = max(20,8) = 20
Step 5: i=4
- Inner Loop (j-loop): Iterates j from 4 to 5.
- j=4:
- currArea = (4-4) * min(height[4], height[4]) = 0
- maxArea = max(20,0) = 20
- j=5:
- currArea = (5-4) * min(height[4], height[5]) = 1 * min(4, 5) = 4
- maxArea = max(20,4)=20
Step 6: i=5
- Inner Loop (j-loop): j=5.
- j=5:
- currArea = (5-5) * min(height[5], height[5]) = 0
- maxArea = max(20,0) = 20
Step 7: Return maxArea.
Steps to write code
Step 1: Initialize Maximum Area
- maxArea keeps track of the largest area found during the iteration over all pairs of lines.
- The size of the height array is stored in n to determine the range for iterating over all pairs.
Step 2: Outer Loop
- The outer loop goes through each element of the array height and considers it as the first line of a pair. It runs from i = 0 to n - 1.
Step 3: Inner Loop
- The inner loop starts at index i and runs until n-1, considering each element as the second line of the pair.
Step 4: Calculate Current Area
- For each pair (i, j), the area is calculated as: currArea=(j−i)×min(height[i], height[j]) Here:
- width is j - i (distance between the two lines).
- height is the shorter of the two lines, given by min(height[i], height[j]).
Step 5: Update Maximum Area
- After calculating currArea, check if it's larger than the current maxArea. If so, update maxArea.
Step 6: Repeat for All Pairs
- The outer loop goes through all possible first lines, and the inner loop goes through all possible second lines. This means every possible pair of lines is considered for calculating the area.
Step 7: Return Maximum Area
- After both loops finish, the maxArea holds the largest container area found among all pairs. The function returns this value.
Brute Force in All Languages
C++
class Solution {
public:
int maxArea(vector<int>& height) {
// Initialize the variable denoting maximum area.
int maxArea = 0;
int n = height.size();
// Nested loops to get all pairs.
for (int i = 0; i < n; ++i) {
for (int j = i; j < n; ++j) {
// For each pair calculate its area.
int currArea = (j - i) * min(height[i], height[j]);
// Maximize the area in maxArea.
maxArea = max(currArea, maxArea);
}
}
// Return the maxArea.
return maxArea;
}
};Java
public class Solution {
public int maxArea(int[] height) {
// Initialize the variable denoting maximum area.
int maxArea = 0;
int n = height.length;
// Nested loops to get all pairs.
for (int i = 0; i < n; ++i) {
for (int j = i; j < n; ++j) {
// For each pair calculate its area.
int currArea = (j - i) * Math.min(height[i], height[j]);
// Maximize the area in maxArea.
maxArea = Math.max(currArea, maxArea);
}
}
// Return the maxArea.
return maxArea;
}
}Python
class Solution:
def maxArea(self, height: List[int]) -> int:
# Initialize the variable denoting maximum area.
max_area = 0
n = len(height)
# Nested loops to get all pairs.
for i in range(n):
for j in range(i, n):
# For each pair calculate its area.
curr_area = (j - i) * min(height[i], height[j])
# Maximize the area in max_area.
max_area = max(curr_area, max_area)
# Return the max_area.
return max_areaJavascript
/**
* @param {number[]} height
* @return {number}
*/
var maxArea = function(height) {
let maxArea = 0;
const n = height.length;
// Nested loops to calculate all pairs
for (let i = 0; i < n; i++) {
for (let j = i; j < n; j++) {
// Calculate the current area
const currArea = (j - i) * Math.min(height[i], height[j]);
// Update maxArea
maxArea = Math.max(currArea, maxArea);
}
}
return maxArea;
};Time Complexity: O(n²)
Outer Loop:
- The outer loop runs from i=0 to i=n−1. Thus, the total number of iterations for the outer loop is n.
Inner Loop:
- For a fixed value of i, the inner loop runs from j=i to j=n−1.
- The number of iterations for the inner loop depends on the current value of i. Specifically, the inner loop executes n−i iterations for each i.
Total Iterations:
- The total number of iterations of the inner loop across all i is given by:
Total number of iterations: n + (n-1) + (n-2) + (n-3) …. + 1
- This is the sum of the first n natural numbers, which equals:
Total number of iterations= n * (n+1) / 2
Final Time Complexity:
- The total number of iterations for the nested loops is n * (n+1) / 2.
- In Big-O notation, we ignore constant factors and lower-order terms, so the time complexity of the nested loops is O(n²).
- Inside the inner loop, the operations involve:
- Calculating the area: (j−i) × min(height[i], height[j] ) → O(1).
- Updating the maximum area: max(currArea, maxArea)
- These operations are constant time O(1) and are performed once per iteration of the nested loops.
So, the overall total time complexity is O(n²).
Space Complexity: O(1)
Auxiliary Space Complexity : refers to the additional or extra space used by an algorithm, excluding the space required to store the input data.
- Variables Used:
- maxArea : Stores the maximum area, a single integer O(1).
- n : Stores the size of the height array, a single integer O(1).
- Loop variables i and j: Two integer variables O(1).
- Temporary variables inside the loop:
- currArea: Stores the area calculated for each pair, an integer O(1).
Thus, the auxiliary space complexity is O(1)
Total Space Complexity
- Input Array:
- The input array height is passed by reference to the function. While it doesn’t contribute to auxiliary space, it is part of the overall memory required to execute the program.
- For an array of size n, the memory required is O(n).
Thus, the overall total space complexity is: O(n)+O(1) = O(n)
This approach works but requires a significant number of calculations, especially for large arrays, as it checks every possible pair of lines. For n lines, the brute force method performs O(n²) calculations. Given the constraint n ≤ 10, this means 10⁵×10⁵=10¹⁰ calculations.
A system can typically handle around 10⁷ calculations per second. Performing 10¹⁰ calculations in a single second far exceeds this limit, making the brute force approach impractical for larger values of n. Therefore, it becomes essential to optimize the solution to fit within the allowed time frame.
Optimal Approach
Intuition
In the brute force method, we check the area of the container for every possible pair of vertical lines. This results in a time complexity of O(n²). While this approach works for smaller arrays, it becomes inefficient for larger ones because it involves too many calculations. To optimize, we need to find a smarter way to calculate the maximum area without checking every pair.
The area of the container depends on two factors: the width (distance between the two lines) and the height (the shorter of the two lines). An important observation is that the smaller height always limits the container's capacity, no matter how far apart the lines are. To maximize the area efficiently, we need a strategy that brings us closer to taller lines while exploring potential combinations systematically. This is where the two-pointer approach comes into play.
Why Use the Two-Pointer Approach?
Imagine you’re standing at the two farthest ends of the array, where the lines give you the maximum possible width. The area at this point is determined by the smaller of the two heights. Now, think of this: if we want to increase the area, simply moving one of the lines inward allows us to explore new combinations. But which line should we move?
If you move the line with the larger height, the height of the container cannot improve (since the smaller height is still limiting). However, if you move the shorter line, you open up the possibility of finding a taller line, which might lead to a larger area.
Example: [1 4 3 2 4]
Initially, the pointers are at the two farthest ends (indices 0 and 4, with heights 1 and 4). The area is determined by the smaller height, which is 1. Therefore, the area is 1 * (4 - 0) = 4.
- Now, if we were to move the line with the larger height (index 4, height 4) inward, the height of the container cannot improve because the height is still limited by the smaller height (1). So, moving the taller line is unhelpful.
Instead, we move the line with the smaller height (index 0, height 1) inward. By doing this, we open up the possibility of encountering a taller line, which can increase the area.
- After moving the left pointer to index 1 (height 4), the new area becomes 4 * (4 - 1) = 12, which is larger than the previous area.
This makes the two-pointer strategy efficient because it naturally guides us towards better solutions without wasting time on unnecessary checks.
How Does the Two-Pointer Approach Work?
The two-pointer approach works by placing one pointer at the start of the array and the other at the end. The area of the container is calculated using the lines at these two pointers. Since the smaller height determines the container's capacity, moving the pointer at the taller line won't help increase the area—it keeps the height limited by the shorter line.
Instead, we move the pointer at the shorter line inward. This increases the chance of finding a taller line, which could result in a larger area. By systematically reducing the width and prioritizing potential height increases, this strategy avoids unnecessary comparisons, reducing the time complexity to O(n), making it highly efficient for large arrays.
Dry-run
Input: [2,5,8,4,4,5]
Output: 20
Explanation: This area is obtained by two integers situated at index 2 and 6, hence width is 6-2 = 4 and height is minimum of height[2] and height[6] = 5, giving a total area of 20. There is no other pair which results in a greater area than 20.
Initial Setup:
- maxArea = 0
- left = 0 (points to the first element, which is 2)
- right = 5 (points to the last element, which is 5)
Iteration 1:
- left = 0, right = 5 (comparing height[0] = 2 and height[5] = 5)
- Condition: height[left] <= height[right], so we calculate the area:
- currArea = (right−left)×min(height[left],height[right]) = (5−0)×min(2,5) = 5×2 =10
- Update maxArea: maxArea = max(0,10) =10
- Move left pointer:left++, so now left = 1.
Iteration 2:
- left = 1, right = 5 (comparing height[1] = 5 and height[5] = 5)
- Condition: height[left] <= height[right], so we calculate the area:
- currArea = (right−left)×min(height[left],height[right]) = (5−1)×min(5,5) = 4×5 = 20
- Update maxArea: maxArea = max(10,20) = 20
- Move left pointer:left++, so now left = 2.
Iteration 3:
- left = 2, right = 5 (comparing height[2] = 8 and height[5] = 5)
- Condition: height[left] > height[right], so we calculate the area:
- currArea = (right−left)×min(height[left],height[right]) = (5−2)×min(8,5) = 3×5 = 15
- Update maxArea: maxArea = max(20,15) = 20
- Move right pointer:right--, so now right = 4.
Iteration 4:
- left = 2, right = 4 (comparing height[2] = 8 and height[4] = 4)
- Condition: height[left] > height[right], so we calculate the area:
- currArea = (right−left)×min(height[left],height[right]) = (4−2)×min(8,4) = 2×4 = 8
- Update maxArea: maxArea=max(20,8)=20
- Move right pointer:right--, so now right = 3.
Iteration 5:
- left = 2, right = 3 (comparing height[2] = 8 and height[3] = 4)
- Condition: height[left] > height[right], so we calculate the area:
- currArea = (right−left)×min(height[left],height[right]) = (3−2)×min(8,4) = 1×4 = 4
- Update maxArea: maxArea=max(20,4)=20
- Move right pointer:right--, so now right = 2.
Termination:
- At this point, left = 2 and right = 2, so the loop ends.
Final Output:
- The maximum area found during the iterations is maxArea = 20.
Thus, the final output is 20, which corresponds to the container formed by lines at index 1 and 5 (height values 5 and 5), with a width of 5 - 1 = 4 and a height of 5. The area is 5 * 4 = 20.
Steps to write code
Step 1: Initialize Maximum Area and Pointers
- maxArea will hold the largest area found during the iteration.
- We initialize two pointers, left at the start of the array and right at the end.
Step 2: Start the Loop with Two Pointers
- The while loop runs as long as the left pointer is smaller than the right pointer. This ensures that we are comparing valid pairs of lines.
Step 3: Calculate the Area for the Current Pair of Lines
- For each pair of lines at indices left and right, we calculate the area:
- currArea = (right−left)×min(height[left],height[right])
- Width is the distance between the two pointers: (right - left).
- Height is the shorter of the two lines, given by min(height[left], height[right]).
Step 4: Update Maximum Area
- After calculating the area for the current pair, we compare it with the current maxArea. If currArea is greater, we update maxArea. This ensures that maxArea always stores the largest area found.
Step 5: Move the Pointer for the Shorter Line
- If height[left] <= height[right]:
- We move the left pointer inward by incrementing it (left++). This is because the line at left is shorter, and by moving left inward, we may find a taller line that could increase the area.
- If height[right] < height[left]:
- We move the right pointer inward by decrementing it (right--). This is because the line at right is shorter, and moving right inward might give us a taller line that could potentially increase the area.
Step 6: Repeat the Process Until the Pointers Meet
- The process of calculating the area, updating the maximum area, and adjusting the pointers continues until the left and right pointers meet, ensuring all potential containers are evaluated.
Step 7: Return the Maximum Area
- After the loop finishes, the variable maxArea will contain the largest area found. We return maxArea as the result.
Optimal Approach in All Languages
C++
class Solution {
public:
int maxArea(vector<int>& height) {
int maxArea = 0;
// Initialize the two pointers.
int left = 0, right = height.size() - 1;
// Loop until the pointers are away from each other.
while (left < right) {
if (height[left] <= height[right]) {
// Maximize the maxArea.
maxArea = max(maxArea, (right - left) * height[left]);
// Move the left pointer.
left++;
} else {
// Maximize the maxArea.
maxArea = max(maxArea, (right - left) * height[right]);
// Move the right pointer.
right--;
}
}
// Return the result.
return maxArea;
}
};Java
class Solution {
public int maxArea(int[] height) {
int maxArea = 0;
// Initialize the two pointers.
int left = 0, right = height.length - 1;
// Loop until the pointers meet.
while (left < right) {
if (height[left] <= height[right]) {
// Maximize the maxArea.
maxArea = Math.max(maxArea, (right - left) * height[left]);
// Move the left pointer forward.
left++;
} else {
// Maximize the maxArea.
maxArea = Math.max(maxArea, (right - left) * height[right]);
// Move the right pointer backward.
right--;
}
}
// Return the maximum area.
return maxArea;
}
}Python
class Solution:
def maxArea(self, height: List[int]) -> int:
max_area = 0
# Initialize the two pointers.
left, right = 0, len(height) - 1
# Loop until the pointers meet.
while left < right:
if height[left] <= height[right]:
# Maximize the max_area.
max_area = max(max_area, (right - left) * height[left])
# Move the left pointer forward.
left += 1
else:
# Maximize the max_area.
max_area = max(max_area, (right - left) * height[right])
# Move the right pointer backward.
right -= 1
# Return the maximum area.
return max_areaJavascript
/**
* @param {number[]} height
* @return {number}
*/
var maxArea = function(height) {
let maxArea = 0;
// Initialize the two pointers.
let left = 0, right = height.length - 1;
// Loop until the pointers meet.
while (left < right) {
if (height[left] <= height[right]) {
// Maximize the maxArea.
maxArea = Math.max(maxArea, (right - left) * height[left]);
// Move the left pointer forward.
left++;
} else {
// Maximize the maxArea.
maxArea = Math.max(maxArea, (right - left) * height[right]);
// Move the right pointer backward.
right--;
}
}
// Return the maximum area.
return maxArea;
};Time Complexity : O(n)
Initial Setup
- maxArea is initialized to 0: O(1) (constant time).
- The two pointers, left and right, are initialized: O(1) (constant time).
- The length of the height array is determined by height.size(): O(1) (constant time).
Thus, the initial setup of variables and pointer initialization takes O(1).
While Loop
The while loop iterates as long as left is less than right. Each iteration compares and possibly updates the maximum area. The important part to focus on is how many iterations the loop runs.
- The loop runs as long as left < right.
- At each step, either left is incremented or right is decremented.
- Therefore, both pointers move toward each other, and they meet when left equals right.
Since left starts at 0 and right starts at n - 1 (where n is the length of the height array), each pointer moves at most n steps, and the total number of iterations will be at most n.
Inside the Loop
In each iteration, the following operations occur:
- Comparing the values of height[left] and height[right]: O(1).
- Calculating the area (right - left) * height[left] or (right - left) * height[right]: O(1).
- Updating the maximum area with maxArea = max(maxArea, ...): O(1).
- Incrementing or decrementing one of the pointers (left++ or right--): O(1).
All these operations inside the loop take constant time O(1) per iteration.
Overall Time Complexity
- The while loop runs n−1 times, which is approximately O(n) iterations.
- In each iteration, the operations inside the loop are all constant time O(1).
Therefore, the overall time complexity of this code is O(n).
Space Complexity : O(1)
Auxiliary Space Complexity
Auxiliary space is the extra space used by the algorithm excluding the input data. Let's analyze the algorithm step by step:
- Variables:
- maxArea: A single integer variable initialized to store the maximum area.
- left and right: Two integer variables used as pointers.
- These variables consume O(1) space because they are simple scalar variables.
- Temporary Computations:
- During the while loop, temporary values such as (right - left) * height[left] or (right - left) * height[right] are computed. However, these are not stored and are evaluated in constant time. Thus, they don’t contribute to additional space usage.
Since the algorithm does not use recursive calls, dynamic allocations, or extra data structures, the auxiliary space complexity is O(1).
Total Space Complexity
The total space complexity analysis accounts for both auxiliary space and the additional space required for the input.
Input Space
The input data structure height has a space complexity of O(n), where n is the size of the array. This space is required to store the heights of the lines.
Since this input is provided to the function and not created within the algorithm, this does not contribute to the algorithm's additional space usage.
The total space complexity of the algorithm is the sum of:
- Auxiliary Space: O(1)
- Input Space: O(n)
Thus, the total space complexity is: O(1) + O(n) = O(n)
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems: -
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
You are given an array of positive integers price where price[i] denotes the price of the iᵗʰ candy and a positive integer k.
The store sells baskets of k distinct candies. The tastiness of a candy basket is the smallest absolute difference of the prices of any two candies in the basket.
Return the maximum tastiness of a candy basket.