LESSON 229 OF 338 · TWO POINTERS

Container With Most Water in Go: Two Pointers in O(n) Time

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

Container With Most Water in Go, explained

Problem overview

The function maxArea receives a slice of non-negative integers, height. Each value is the height of a vertical line, and the lines stand side by side at positions 0, 1, 2 and so on. Choose two lines. Together with the x-axis they form a container, and the function returns the largest amount of water such a container can hold. The container can't be tilted, and there are at least two lines.

For [1, 8, 6, 2, 5, 4, 8, 3, 7] the answer is 49. The lines of height 8 (position 1) and 7 (position 8) are 7 apart, and the water level is capped by the shorter of the two: 7 * 7 = 49.

Approach: start wide, discard the shorter line

The area of a container is min(height[left], height[right]) * (right - left): the shorter line decides the water level, and the distance between the lines is the width. Trying every pair is O(n²).

The two-pointer idea starts with the widest container, the first and last lines, and then narrows it. Each step must give up one line, and the argument for which one is simple. Suppose the left line is the shorter. Any container that keeps this left line and uses a line closer than the current right one is narrower, and its height is still capped by the left line, so it can't beat the current area. The left line has therefore been fully explored and can be dropped. Moving the pointer of the taller line would throw away a line that could still pair with something better.

So at every step: compute the area, update the best, and move the pointer that sits on the shorter line inward. When the heights are equal, either pointer may move. The loop takes at most n - 1 steps.

On the example, the first pair is heights 1 and 7 at distance 8, an area of 8. The left line is shorter, so left moves. The next pair, 8 and 7 at distance 7, gives 49. The remaining pairs never exceed it.

Step by step

Declare three variables at once: result at 0 for the best area, left at 0 and right at len(height)-1, the last index.
Loop while left < right. Go has no while, so this is a condition-only for. When the pointers meet, there is no pair left.
Compute area as the smaller of the two heights times right - left. Water above the shorter line would spill over it, so the minimum is used, not the maximum.
Update result with max(result, area), so it never decreases.
If height[left] < height[right], do left++: the left line is the shorter, and only moving it can lead to a bigger container.
Otherwise do right--. This covers the case where the right line is shorter, and also equal heights.
Return result after the loop.

The solution in Go

func maxArea(height []int) int {
    result, left, right := 0, 0, len(height)-1
    for left < right {
        area := min(height[left], height[right]) * (right - left)
        result = max(result, area)
        if height[left] < height[right] {
            left++
        } else {
            right--
        }
    }
    return result
}

The Go details worth a closer look:

Built-in min and max. Since Go 1.21 both are part of the language, work on any ordered type and accept two or more arguments. No import is needed. Older versions require writing your own helper functions.
Multiple declaration. result, left, right := 0, 0, len(height)-1 declares three variables with one :=. All three are int, and the right-hand side is evaluated before any assignment.
Increment is a statement. left++ and right-- can't be used inside an expression, so each stands on its own line.
Unused variables are errors. Every variable here is read, which is what lets the program compile.
Integer arithmetic. All values are int, 64-bit here. The product of a height and a distance would need very large inputs to overflow, and the wrap-around is silent.
The input is only read. The function never changes height.

Complexity

Time: O(n). Every iteration moves one pointer inward, so the pointers meet after exactly n - 1 iterations, each doing constant work.

Space: O(1). The function keeps three integers and the current area.

Edge cases and common mistakes

Two lines. [1, 1] gives 1: one iteration, with width 1 and height 1.
Zero heights. [0, 0] gives 0.
Equal heights. [5, 5, 5] gives 10, from the outer pair, with width 2. Moving either pointer on a tie is safe.
The tallest lines are not always the answer. In [4, 3, 2, 1, 4] the best container is the two outer lines of height 4, at distance 4, giving 16. A tall line in the middle would give a narrow container.
A tall line between short ones. [1, 2, 1] gives 2: the outer pair gives 1 * 2, and pairing the 2 with a 1 gives 1 * 1.
Using the larger height. The water level is set by the shorter line. Taking the maximum overstates the area.
Forgetting the width. The area is height times distance, and the distance is right - left, not the number of lines.
Moving the taller pointer. That can only shrink the width without raising the cap, and it can skip the best pair.

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.
[5, 5, 5] gives 10.

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

Start learning free