LESSON 257 OF 415 · TWO POINTERS

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

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

SWIFT · TWO POINTERS

Container With Most Water in Swift, explained

Problem overview

The method maxArea receives an array height of non-negative integers. Entry i is a vertical line at position i with that height. Pick any two lines: together with the x-axis they form a container. The amount of water it holds is the area of a rectangle. The width is the distance between the two lines, and the height is the shorter of the two lines, because water above it would spill over. The method returns the largest area any pair can hold.

For [1, 8, 6, 2, 5, 4, 8, 3, 7] the best pair is the line of height 8 at index 1 and the line of height 7 at index 8. The width is 7, the height is min(8, 7) = 7, and the area is 49.

Approach: start wide and move the shorter line

Checking every pair takes O(n²) time. Two pointers do it in one pass.

Start with the widest container: left at the first line and right at the last. Compute its area. Now one of the pointers must move inward, which makes the container narrower. Which one?

The shorter line caps the height. If you move the taller line inward, the width shrinks and the height is still capped by the same shorter line, or by something even shorter. The new container can't be larger. So the only move that could ever help is to move the shorter line, hoping to meet a taller one. This is safe: every container that uses the shorter line with any partner further in is narrower and no taller, so it can be skipped without being checked.

Repeat until the pointers meet, remembering the best area seen. Each step moves one pointer, so the loop runs at most n - 1 times.

A quick trace on [1, 8, 6, 2, 5, 4, 8, 3, 7]: the first container is lines 1 and 7, with area min(1, 7) * 8 = 8. The left line is shorter, so left moves to the 8. Now min(8, 7) * 7 = 49 is the best so far. The right line is shorter, so right moves in, and the narrower containers that follow never beat 49.

Why does discarding lose nothing? Say the left line, at position a, is not taller than the right line, at position r. Any other container that uses line a has its other line somewhere between a and r, so it is narrower than the one just measured. Its height is also capped by line a, which is the same cap. So its area is at most the area already recorded, and line a can be dropped.

Step by step

Set up the variables on one line: result at 0, left at 0 and right at height.count - 1.
Loop while left < right. When they meet, there is no pair left.
Compute the area as min(height[left], height[right]) * (right - left): the shorter line times the distance.
Keep the best with max(result, area), so result never goes down.
Move the shorter side. If height[left] is smaller than height[right], advance left.
Otherwise, pull right back. This branch also covers equal heights, where moving either pointer is safe.
Return result.

The solution in Swift

class Solution {
    func maxArea(_ height: [Int]) -> Int {
        var result = 0, left = 0, right = height.count - 1
        while left < right {
            let area = min(height[left], height[right]) * (right - left)
            result = max(result, area)
            if height[left] < height[right] {
                left += 1
            } else {
                right -= 1
            }
        }
        return result
    }
}

Swift details worth knowing:

Global min and max. They are free functions that take two values, with no receiver and no import.
Several variables in one declaration. var result = 0, left = 0, right = height.count - 1 declares three Int variables. They are all var, since all three change.
let area is a constant created fresh on each pass of the loop.
No ++ or --. Swift uses left += 1 and right -= 1.
Overflow. Swift traps on integer overflow rather than wrapping, but an area only overflows a 64-bit Int for heights in the billions combined with billions of lines, so it isn't a practical concern here.

Complexity

Time: O(n). Each iteration moves one pointer one step toward the other, so the loop ends after at most n - 1 iterations, and each iteration does constant work.

Space: O(1). Only a few integers are used, 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. A container whose shorter line has height 0 holds nothing.
A tall line in the middle. [1, 2, 1] gives 2. The two outer lines hold min(1, 1) * 2 = 2, and the tall middle line can't help because the water is limited by the outer ones.
Tall lines at the ends. [4, 3, 2, 1, 4] gives 16, the widest container with both lines of height 4.
Using the taller line for the height. The result would count water that spills over.
Moving the taller pointer. It can skip the best pair for good.
Forgetting the width. The width is right - left, not the number of lines.
Fewer than two lines. The lesson promises at least two. If an empty array were passed, right would be -1, the loop would not run and the method would return 0.

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

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

Start learning free