Topic: Learning notes
LeetCode 11: Container With Most Water in TypeScript, Why Move the Shorter Side?
My two-pointer solution, with a brute-force comparison, a proof for discarding the shorter side, and executable checks for O(n) time and O(1) extra space.
I put the pointers at opposite ends of the array and started with the widest container. At each step, I recorded the area and moved the shorter side inward. This note keeps my implementation and adds a brute-force comparison, a correctness proof, and executable tests.
The problem and its area
LeetCode 11: Container With Most Water gives a nonnegative integer array height. A vertical line of height height[i] stands at position i. Choose two lines that form a container with the horizontal axis, and return its maximum area. The container cannot tilt.
The constraints are 2 <= height.length <= 100000 and 0 <= height[i] <= 10000. For endpoints left and right, width is the difference between their indices. The shorter line limits the water level:
area = Math.min(height[left], height[right]) * (right - left)
Intermediate lines do not subtract volume. The task evaluates the two chosen boundaries rather than the rainwater trapped in each hollow.
My two-pointer implementation
function maxArea(height: number[]): number {
let p1 = 0;
let p2 = height.length - 1;
let max = 0
while (p2 > p1) {
const currentArea = Math.min(height[p1], height[p2]) * (p2 - p1)
max = Math.max(max, currentArea)
if (height[p1] < height[p2]) {
p1++;
} else {
p2--;
}
}
return max
};p1 starts on the left and p2 on the right. Each iteration calculates the current area, updates max, and chooses a pointer to move based on the endpoint heights. When the heights match, this code moves the right pointer.
This implementation already runs in linear time with constant extra space. The explanation below supplies the reason each move is safe; it does not require a different algorithm.
Added comparison: enumerate every pair
The following brute-force version was added for this article. It was not my original submitted implementation.
function maxAreaBruteForce(height: number[]): number {
let max = 0;
for (let i = 0; i < height.length; i++) {
for (let j = i + 1; j < height.length; j++) {
max = Math.max(max, Math.min(height[i], height[j]) * (j - i));
}
}
return max;
}There are n * (n - 1) / 2 pairs of distinct positions. Checking them all takes O(n²) time and O(1) extra space. An array of length 100000 has 4,999,950,000 pairs. The two-pointer method avoids pairs that can be proved no better than one already checked.
Why discarding the shorter side is safe
Suppose height[left] <= height[right]. The current area is:
height[left] * (right - left)
Keep the left endpoint and choose any new right endpoint j between the current endpoints. The water level is still at most height[left], while the width shrinks to j - left. Therefore:
min(height[left], height[j]) * (j - left) <= height[left] * (right - left)
The current pair has already been included in the maximum. Every remaining pair using this left endpoint can be discarded, so moving the left pointer is safe. The argument is symmetric when the right side is shorter.
For example, endpoint heights of 2 and 8 at distance 5 give an area of 10. Keep the height-2 left endpoint and move the right endpoint inward by one position. Even if its new height is 100, the area is at most 8. Moving the shorter side allows the height limit to increase, but the next area is not guaranteed to increase. That is why the code keeps the best area seen so far.
When the heights are equal, either endpoint can be discarded. My code handles equality in the else branch and moves the right pointer.
The loop invariant
At the start of each iteration, max holds the largest area among the pairs checked so far. No discarded pair can beat max. Any pair that might improve the answer still has both endpoints within [p1, p2].
Initially, no pairs have been discarded, so the condition holds. Each iteration updates the maximum and then uses the inequality above to discard the shorter endpoint. The condition remains true. Once the pointers meet, no pair of distinct endpoints remains inside the interval. Every candidate has been checked or ruled out, so max is the answer.
Time and extra space
Let n = height.length. The initial distance between the pointers is n - 1. Each iteration reduces it by exactly one, so the loop runs n - 1 times. Time complexity is O(n).
Only a few numeric variables are stored. There is no array or Map whose size grows with the input, so extra space is O(1). The input array is excluded from extra-space accounting and is not modified.
Added verification
The first three cases came from my answer. The checks below turn their expected results into executable assertions and add zero heights, equal heights, increasing heights, and input preservation. Put the implementation and these checks in one TypeScript file and run it in an environment that supports TypeScript execution.
import assert from "node:assert/strict";
assert.equal(maxArea([1, 7, 6, 2, 5, 4, 8, 3, 8]), 49);
assert.equal(maxArea([1, 1]), 1);
assert.equal(maxArea([8, 7, 2, 1]), 7);
assert.equal(maxArea([0, 0]), 0);
assert.equal(maxArea([4, 4, 4, 4]), 12);
assert.equal(maxArea([1, 2, 3, 4]), 4);
assert.equal(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]), 49);
const original = [1, 7, 6, 2, 5, 4, 8, 3, 8];
const snapshot = [...original];
maxArea(original);
assert.deepEqual(original, snapshot);In the first custom case, indices 1 and 8 have heights 7 and 8, giving 7 * 7 = 49. Its input differs from the official example even though both answers are 49. For [8, 7, 2, 1], indices 0 and 1 give the best area of 7.
Verification also enumerated all 21,840 arrays of lengths 2 through 7 with heights from 0 through 3. The two-pointer and brute-force results matched. This check helps catch implementation errors; the elimination argument above establishes correctness for all valid inputs.
Pitfalls and a reusable idea
Width is p2 - p1, not the number of elements including both endpoints, so do not add one. Calculate the area and update the maximum before moving a pointer. Sorting is also invalid because it changes the original distances between positions.
This problem gives a reason for each pointer move. For another problem that shrinks a search interval, ask why every discarded candidate is guaranteed to be no better than a result already considered.