Problem overview
The method maxArea(height: Array[Int]) receives non-negative integers. Entry i is a vertical line at position i whose height is height(i). Any two lines, together with the x-axis, form a container. The method returns the largest amount of water such a container can hold. The container can't be tilted, and there are at least two lines.
The water level is limited by the shorter of the two lines, and the width is the distance between them, so the area of a container is min(height(left), height(right)) * (right - left).
For [1, 8, 6, 2, 5, 4, 8, 3, 7] the best pair is the 8 at index 1 and the 7 at index 8. The shorter line is 7 and the distance is 7, so the area is 49.
Approach: start wide, move the shorter line
Trying every pair of lines is correct but takes O(n²). The two-pointer method needs one pass.
Start with the widest container: left at the first line and right at the last. Measure its area and keep the best so far. Now one pointer has to move inward, which makes the container narrower. The question is which one.
Moving the taller line can't help. The new container is narrower and its height is still capped by the shorter line, which hasn't changed, so its area is no larger than before. Moving the shorter line is the only move that can make the area grow, because the next line might be tall enough to raise the cap. So the pointer at the shorter line moves. Every container that was skipped has been ruled out as no better than the one just measured.
When the pointers meet there are no pairs left, and the best area seen is the answer.
On the example, the first container uses heights 1 and 7: area 1 * 8 = 8. The left line is shorter, so left moves. Next the pair is 8 and 7 with width 7: area 49. The right line is the shorter one, so right moves, and the remaining pairs never beat 49.
Step by step
- Declare three variables.
resultstarts at 0,leftat 0 andrightatheight.length - 1. The solution puts them on one line, separated by semicolons. - Loop while
left < right. A container needs two different lines. - Compute the area as the smaller of the two heights,
math.min(height(left), height(right)), multiplied by the distanceright - left. - Keep the best:
result = math.max(result, area). - If
height(left) < height(right), doleft += 1: the left line is the limit, so it is the one to replace. - Otherwise, do
right -= 1. When the heights are equal, moving either side is safe, and this branch movesright. - Return
result.
The solution in Scala
class Solution {
def maxArea(height: Array[Int]): Int = {
var result = 0; var left = 0; var right = height.length - 1
while (left < right) {
val area = math.min(height(left), height(right)) * (right - left)
result = math.max(result, area)
if (height(left) < height(right)) {
left += 1
} else {
right -= 1
}
}
return result
}
}
The Scala details worth knowing:
- Semicolons. Scala ends a statement at the end of the line, so semicolons are optional. They are only needed to put several statements on one line, as in the first line of the body.
math.minandmath.max.mathis Scala's own package and needs no import. Both take two numbers and return one.valinside the loop.areais created fresh on every iteration and never changes, sovalfits. The values that do change,result,leftandright, arevars.- Parentheses for indexing. It is
height(left), notheight[left]. Intis 32 bits. An area above 2147483647 would wrap silently, which only matters for very large heights on very long arrays.
Complexity
Time: O(n). Each iteration moves one pointer inward, so the loop runs at most n - 1 times, and each iteration does constant work.
Space: O(1). The method uses a handful of integers.
Edge cases and common mistakes
- Two lines.
[1, 1]gives 1: height 1, width 1. - Zero heights.
[0, 0]gives 0, since water can't rise above a line of height 0. - Equal heights.
[5, 5, 5, 5]gives 15, from the two outer lines. - A tall pair far apart.
[4, 3, 2, 1, 4]gives 16, from the two 4s. The height of the lines in between doesn't matter. - Using the maximum instead of the minimum. Water above the shorter line would spill, so the height of a container is the smaller of the two lines.
- Moving the taller line. That can only shrink the width without raising the cap, and it can discard the best pair.
- Forgetting the width. The area is height times distance, not just height.
- Fewer than two lines. The problem guarantees at least two. For an array with 0 or 1 entries the loop never runs, and the method returns 0.
Testing
[1, 8, 6, 2, 5, 4, 8, 3, 7]gives49.[1, 1]gives1.[4, 3, 2, 1, 4]gives16.[1, 2, 1]gives2.[2, 3, 4, 5, 18, 17, 6]gives17.
