
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:
- 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]
andheight[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.
- Start with two pointers, one at the beginning (
Example walkthrough:
- For the array
[1,8,6,2,5,4,8,3,7]
:- Starting with
left = 0
andright = 8
, the minimum height is1
(fromheight[0]
), and width is8
. Area calculation gives1 * 8 = 8
. - Increment
left
(sinceheight[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 indices1
and8
.
- Starting with
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
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 vectorbars
as an argument, representing the heights of the bars. - Variables
maxWater
,i
, andj
are initialized.maxWater
is to store the maximum volume of water found,i
is set to the start of the vector, andj
to the end. - A while loop is used to process elements between
i
andj
:- Calculate the distance between
i
andj
. maxWater
is updated to the higher value between its current value and the water contained between barsi
andj
, 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
andj
, incrementi
ifbars[i]
is smaller or equal, else decrementj
.
- Calculate the distance between
- The loop iterates until
i
andj
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.
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
andend
, 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 atstart
andend
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]
andbars[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 updatemaxWater
if the current area is larger. - Decide which pointer to move: move the
start
pointer right if the bar atstart
is shorter or equal to the bar atend
(as possibly a taller bar towards the center might help contain more water), otherwise move theend
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.
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
:
- Initialize
area
to 0 to keep track of the largest area found. - Use two pointers
start
andend
to represent the indices of the line at the beginning and the end of the array, initializingstart
to 0 andend
tosize - 1
. - While
start
is less thanend
:- Calculate the distance between the two pointers.
- Compute the area formed between the lines at indices
start
andend
, which is the product of the smaller height and the distance. Use themaximum
function to updatearea
if a larger area is found. - To potentially find a larger area, decide whether to move the
start
pointer or theend
pointer. If the height atstart
is less than or equal to the height atend
, increment thestart
pointer; otherwise, decrement theend
pointer.
- 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.
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 thanend
. Calculate thewidth
as the difference betweenend
andstart
. - 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 thewidth
. - Depending on which side is shorter, move the corresponding pointer inward (
start++
if the left side is shorter, otherwiseend--
). - 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.
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
andend
, pointing at the beginning and the end of the bars list respectively. - Use a
while
loop to continue the procedure as long asstart
is less thanend
. - For each iteration, compute the
distance
between thestart
andend
pointers. Calculate tentative water containment by computing the area formed between the bars at thestart
andend
pointers, which is given by the minimum height of the two bars multiplied by the distance between them. Updatemax_water
if this area is greater than the currentmax_water
. - To move the pointers efficiently, compare the heights at
start
andend
. Increment thestart
pointer if the bar atstart
is less than or equal to the bar atend
, otherwise decrement theend
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.
No comments yet.