LESSON 233 OF 348 · TWO POINTERS

Container With Most Water in TypeScript: O(n) with Two Pointers

You are given n non-negative integers a₁, a₂, ..., a_n, where each represents a point at coordinate (i, a_i). n vertical lines are drawn such that the two endpoints of line i are (i, a_i) and (i, 0). Find two lines, which together with the x-axis form a container, such that this container contains the most water.

Note: You may not slant the container and n is at least 2.

The above vertical lines are represented by the array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) one container can contain is 49.

Example:

Input: [1,8,6,2,5,4,8,3,7]
Output: 49

STEP 1 OF 7

Guided

Ctrl + Enter to check

TYPESCRIPT · TWO POINTERS

Container With Most Water in TypeScript, explained

Problem overview

The method maxArea receives an array height of non-negative integers. Think of each value as a vertical line drawn at its index: the line at index i goes from the x-axis up to height[i]. Pick any two lines and the x-axis, and you get a container. The container can't be tilted. The task is to return the largest amount of water any container can hold. The array has at least two lines.

The water in a container forms a rectangle. Its width is the distance between the two indices, and its height is the shorter of the two lines, because water above the shorter line would spill over it. For [1, 8, 6, 2, 5, 4, 8, 3, 7], the best container uses the lines at indices 1 and 8, with heights 8 and 7. The width is 8 - 1 = 7, the height is min(8, 7) = 7, and the area is 49.

Approach: start wide, move the shorter line

The brute-force solution computes the area for every pair of lines, which takes O(n²) time. A pair of pointers does it in a single pass.

Start with the widest container: one pointer at the first line, one at the last. Compute its area and keep it if it is the best so far. Then decide which pointer to move inward. Moving either one makes the container narrower, so the only way to get a bigger area is a taller limiting line.

The shorter line is the limiting one. If you move the taller pointer instead, the width shrinks and the height is still capped by the same short line, so the area can't grow. That means any container that keeps the short line with a narrower width is no better than the one you just measured, so the short line can be discarded for good. Move the pointer at the shorter line inward and repeat.

Each step moves one pointer, and the loop ends when they meet. That is at most n - 1 steps.

On [1, 8, 6, 2, 5, 4, 8, 3, 7], the first container, with lines 1 and 7 at distance 8, holds 1 * 8 = 8. The left line is shorter, so the left pointer moves. Next come 8 and 7 at distance 7, which gives 49. Nothing later beats it.

Step by step

Declare three variables: result starts at 0 and holds the best area. left starts at 0 and right at height.length - 1, the last index.
Loop while left < right. When the pointers meet there is no pair left to form a container.
Compute area. Take Math.min of the two heights, because the shorter line sets the water level, and multiply by right - left, the width.
Update result with Math.max(result, area), so it never decreases.
If height[left] < height[right], do left++. The left line is the limiting one, and keeping it can't help.
Otherwise do right--. The right line is no taller than the left one. When the heights are equal, moving either pointer is safe, and this branch moves the right one.
Return result after the loop.

The solution in TypeScript

class Solution {
    maxArea(height: number[]): number {
        let result = 0, left = 0, right = height.length - 1;
        while (left < right) {
            let area = Math.min(height[left], height[right]) * (right - left);
            result = Math.max(result, area);
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return result;
    }
}

The TypeScript details worth a closer look:

One let, several variables. let result = 0, left = 0, right = height.length - 1; declares three variables. TypeScript infers number for each, so no annotations are needed.
Math.min and Math.max take any number of numbers and return the smallest or the largest. Here each gets two arguments.
Numbers are doubles. There is no integer overflow, and products stay exact up to 2^53. That is far beyond any realistic area here.
Index reads are unchecked. Reading height[i] outside the array gives undefined at run time. The loop condition keeps both pointers inside the array, so every read is a real height.

Complexity

Time: O(n). Each iteration moves one pointer one step inward, and the pointers start n - 1 apart, so the loop runs at most n - 1 times. Every iteration does constant work.

Space: O(1). The method keeps a few numbers, whatever the size of the input.

Edge cases and common mistakes

Two lines. [1, 1] gives 1: the width is 1 and the height is 1.
Zero heights. [0, 0] gives 0, since a container with a zero-height wall holds no water.
Low lines in the middle. In [4, 3, 2, 1, 4], the best container is the widest one, formed by the two 4s, and the method returns 16. The low lines between them don't matter, since only the two walls and their distance count.
Using the taller line for the height. Math.max instead of Math.min overestimates the water, because the shorter wall decides the level.
Measuring the width as right - left + 1. The width is the distance between the lines, not the number of positions they cover. For lines at indices 0 and 1 the width is 1.
Moving the taller pointer. It can skip the best container, because the short line stays in place and the width only shrinks.

Testing

[1, 8, 6, 2, 5, 4, 8, 3, 7] gives 49.
[1, 1] gives 1.
[4, 3, 2, 1, 4] gives 16.
[1, 2, 1] gives 2.
[2, 3, 10, 5, 7, 8, 9] gives 36.

Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free