LESSON 259 OF 414 · TWO POINTERS

Container With Most Water in Rust: 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

Container With Most Water in Rust, explained

Problem overview

The function max_area receives a vector height of non-negative integers. Each number is a vertical line standing at its own position, so the line at index i has height height[i]. Pick two lines. Together with the x-axis they form a container, and the task is to find the largest amount of water any such container can hold. The container can't be tilted, and there are at least two lines.

The water level is limited by the shorter of the two lines, and the width is the distance between their indices. So the area for lines left and right is min(height[left], height[right]) * (right - left). For [1, 8, 6, 2, 5, 4, 8, 3, 7] the best pair is the lines at indices 1 and 8, with heights 8 and 7: min(8, 7) * 7 = 49.

Approach: start wide, move the shorter line

Trying every pair costs O(n²). The two-pointer idea gets it down to O(n) by never looking at a pair that can't win.

Start with the widest container, with left at the first line and right at the last. Compute its area, then shrink the width by one by moving one of the pointers. The key question is which one. Suppose the left line is the shorter. Any container that keeps this left line and uses a closer right line has a smaller width, and its height is still capped by the left line, which is no taller than before. Its area can't be larger than the current one. So the left line is useless in every other pairing, and moving it loses nothing. The same holds for the right line when it is the shorter one. Moving the taller line, by contrast, could throw away the best answer.

Each step discards one line, so the pointers meet after n - 1 steps, and the maximum over all the areas seen is the answer.

Step by step

Declare the state. result is a mutable i32 starting at 0, and left and right are mutable usize indices at the two ends of height. The last index is height.len() - 1.
Loop while left < right. When they meet, no pair of lines is left.
Compute the area. Take the shorter of the two heights with min, and multiply by the distance right - left, cast with as i32 so it matches the i32 heights. The cast applies to the parenthesized distance only, because as binds tighter than *.
Keep the best. result = result.max(area). The max method returns the larger of the two values, so result never decreases.
Move the left pointer with left += 1 when height[left] < height[right].
Otherwise move the right pointer with right -= 1. This covers the case where the right line is the shorter, and also ties. With equal heights, moving either pointer is safe, because a container that keeps one of two equal lines and gets narrower can't be larger.
Return result as the final expression, without a semicolon.

The solution in Rust

impl Solution {
    fn max_area(height: Vec<i32>) -> i32 {
        let mut result: i32 = 0;
        let mut left: usize = 0;
        let mut right: usize = height.len() - 1;
        while left < right {
            let area = height[left].min(height[right]) * (right - left) as i32;
            result = result.max(area);
            if height[left] < height[right] {
                left += 1;
            } else {
                right -= 1;
            }
        }
        result
    }
}

Rust details worth knowing:

min and max are methods. For integers, a.min(b) and a.max(b) come from the Ord trait. They return a value, so they are used as result = result.max(area), not as statements that update in place.
Mixed integer types. right - left is a usize and the heights are i32, and Rust never converts between integer types on its own. The explicit as i32 is required. The subtraction itself is safe because the loop guarantees right > left.
Why right can be decremented. In the else branch, right > left >= 0, so right is at least 1.
Indexing panics. Reading height[left] outside the vector stops the program, rather than returning garbage. Here both pointers stay inside.
Type annotations. let mut result: i32 = 0; and let mut left: usize = 0; spell the types out. Rust would infer them, but the annotation documents which integer type each variable has.

Complexity

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

Space: O(1). The function uses three variables and an area.

Edge cases and common mistakes

Two lines. [1, 1] gives 1: one iteration, width 1, height 1.
Zero heights. [0, 0, 0] gives 0, because every container's height is 0.
The best pair isn't the tallest. [1, 2, 1] gives 2: the two 1s are width 2 apart, and 1 * 2 = 2. [4, 3, 2, 1, 4] gives 16, from the two outer 4s, even though the middle lines are shorter.
Tall lines far apart. [5, 0, 0, 0, 5] gives 20. The empty space between the lines still counts toward the width.
Using the taller line's height. Water spills over the shorter line, so the height is min, never max.
Moving the wrong pointer. Moving the taller one can only shrink the width without raising the height cap, and it can discard the best container.
Empty input. The statement guarantees at least two lines. With an empty vector, height.len() - 1 wraps in an optimized build, and the first height[left] panics with index out of bounds.
Overflow. The area is computed in i32, so a very large area wraps silently in an optimized build, and panics in a debug build. For example, 100,000 lines of height 100,000 have a true best area of 9,999,900,000, which doesn't fit in an i32. An i64 would hold it.

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, 0, 0, 0, 5] gives 20.
[1, 2, 3, 4, 5] gives 6.

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

Start learning free