14 · Container With Most Water

In an Xcode test target:

import Testing

struct ContainerWithMostWaterTests {

    @Test(arguments: [
        ([2, 7, 3, 6, 4, 8, 1], 28),
        ([5, 1, 1, 1, 5], 20),
        ([4, 4], 4),
    ])
    func returnsTheLargestAreaTwoWallsCanHold(heights: [Int], expected: Int) {
        #expect(maxArea(heights) == expected)
    }

    // MARK: - Privates
    private func maxArea(_ heights: [Int]) -> Int {
        0
    }
}

In a playground:

func maxArea(_ heights: [Int]) -> Int {
    0 // your solution
}

let cases: [([Int], Int)] = [
    ([2, 7, 3, 6, 4, 8, 1], 28),
    ([5, 1, 1, 1, 5], 20),
    ([4, 4], 4),
]
for (heights, expected) in cases {
    let got = maxArea(heights)
    print(got == expected ? "PASS" : "FAIL", heights, "→", got, "expected", expected)
}

Two pointers from both ends, moving the weaker side. The cue is "two" entries of an array whose score depends on the distance between them and the smaller of the two. Start with the widest pair — the two outer walls — and walk inward. Every step inward loses one unit of width, so the only step that can ever pay off is one that might raise the shorter wall.

Put one finger on the first wall and one on the last. Work out the water between them and keep the best seen so far. Then move the finger that sits on the shorter wall one step inward, and repeat until the fingers meet.

Why moving the shorter wall is safe: pair the shorter wall with any wall closer in than the other finger, and the water is capped by that shorter wall's height while the width only shrinks — every one of those pairs is worse than the one just measured. So the shorter wall has nothing left to offer, and it can be dropped. Moving the taller wall instead can never help, because the shorter wall still caps the height. On a tie either finger can move: neither wall can do better with anything in between.

Time O(n): each step moves one finger, and they meet after n − 1 steps. Space O(1): two indices and a running best.

func maxArea(_ heights: [Int]) -> Int {
    var left = 0
    var right = heights.count - 1
    var best = 0

    while left < right {
        let area = min(heights[left], heights[right]) * (right - left)
        best = max(best, area)
        if heights[left] < heights[right] {
            left += 1          // the shorter wall caps every narrower pair it's part of
        } else {
            right -= 1
        }
    }
    return best
}

Empty and single-wall input return 0 without a guard: right starts at −1 or 0, the loop condition fails, and nothing is subscripted.

Verified with swift test on Swift 6.4 in Swift 6 mode: the three examples above, six more (empty, one wall, all walls equal, two zero walls, strictly rising heights, two walls at the 10,000 maximum), and 3,000 random arrays checked against a brute-force O(n²) search over every pair.

[2, 7, 3, 6, 4, 8, 1]

Answer 28, after six measurements instead of twenty-one.

[4, 4] — one measurement: 4 × 1 = 4. The walls tie, the right finger moves, the fingers meet. Answer 4.

A slice keeps its parent's indices. The follow-up "now do it for walls 3 to 9 only" tempts you to pass heights[3...9] into a version that takes ArraySlice<Int> or any Collection. Starting left at 0 then reads outside the range, or traps, because the slice's first index is 3, not 0. Start from heights.startIndex and heights.index(before: heights.endIndex), and measure width with heights.distance(from:to:) — or copy into Array(...) first and say why. On a plain [Int] the version above is correct; the moment the signature widens, the integer arithmetic is the bug.

• "Prove the greedy step is right." → Every pair that includes the shorter wall and a wall inside the fingers is no taller and strictly narrower than the pair just measured, so discarding that wall loses nothing. That one sentence is the answer they want.
• "The walls aren't evenly spaced — you get their x positions, sorted." → Same algorithm with width x[right] − x[left]. Width still shrinks every step inward, so the argument still holds.
• "How is this different from trapping rain water?" → There, every wall in between matters and water sits over each position; that needs the running maximum from both sides, not a best pair. Different problem, same two-finger shape: it is problem 16.