Understanding the Two-Pointer Approach
The "Maximum Area Between Bars" problem asks us to find the largest rectangular area that can be formed by selecting any two bars from an array of heights. Each element in the array represents the height of a vertical bar, and the area depends on both the heights of the selected bars and the number of bars that lie between them.
Given an array height[], if we choose bars at positions i and j, the area is calculated as:
Area = min(height[i], height[j]) × (j - i - 1)
The height of the rectangle is limited by the shorter of the two bars because water or any rectangular boundary cannot exceed the smaller height. The width is the number of bars between the selected bars, which is why we use (j - i - 1) instead of (j - i).
Consider the Example
height = [2, 5, 4, 3, 7]
If we select the bars with heights 5 and 7, their indices are 1 and 4. There are two bars between them, so:
Area = min(5, 7) × (4 - 1 - 1)
Area = 5 × 2
Area = 10
This is the maximum possible area for the given array.
A brute-force solution would examine every possible pair of bars. For each pair, it would compute the area and keep track of the maximum value found. Since there are approximately n² pairs, the time complexity becomes O(n²), which is too slow for arrays containing up to 100,000 elements.
To solve the problem efficiently, we use the Two-Pointer Technique.
The Core Idea
The idea is to place one pointer at the beginning of the array and another at the end. These pointers represent the two bars currently being considered. At each step, we calculate the area formed by these bars and update the maximum area if necessary.
The crucial observation is that the area is always limited by the shorter bar. If we move the taller bar inward, the width decreases while the limiting height remains unchanged or becomes even smaller. Therefore, moving the taller bar cannot help us find a larger area.
Instead, we move the pointer that points to the shorter bar. This gives us a chance to find a taller bar that may compensate for the reduced width and produce a larger area.
Algorithm
The algorithm works as follows:
Initialize Two Pointers
Calculate Area
Calculate the area between the bars at these positions.
Update Maximum Area
Update the maximum area found so far.
Move the Shorter Bar
If height[left] < height[right], increment left.
Otherwise, decrement right.
Repeat
Continue until the pointers meet.
This approach ensures that every element is processed at most once, resulting in a linear time complexity of O(n) and constant auxiliary space of O(1).
Java Implementation
class Solution {
public int maxArea(List<Integer> height) {
int left = 0;
int right = height.size() - 1;
int maxArea = 0;
while (left < right) {
int width = right - left - 1;
if (width > 0) {
int currentArea =
Math.min(height.get(left), height.get(right)) * width;
maxArea = Math.max(maxArea, currentArea);
}
if (height.get(left) < height.get(right)) {
left++;
} else {
right--;
}
}
return maxArea;
}
}
Dry Run
Let's perform a quick dry run on the array:
[2, 5, 4, 3, 7]
Initially
left = 0 (height = 2)
right = 4 (height = 7)
width = 3
area = 2 × 3 = 6
Since 2 is smaller than 7, move the left pointer.
Now
left = 1 (height = 5)
right = 4 (height = 7)
width = 2
area = 5 × 2 = 10
Maximum area becomes 10.
Continue moving pointers according to the rule until they meet. No larger area is found, so the final answer is 10.
Common Mistake
The most common mistake in this problem is using j - i as the width.
The problem specifically states that the area depends on the number of bars between the selected bars, making the correct width calculation:
j - i - 1
Conclusion
By combining the width formula with the two-pointer optimization, we obtain an efficient solution that meets the expected constraints and runs comfortably even for very large input sizes.