Problem statement

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.
Link to problem

Example 1

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

Example 2

Input: height = [1,1]
Output: 1

Solutions

Approach 1: Brute Force

Checking all the combinations and determining the maximum, same as usual.
Do remember that the minimum height of two lines will be the height of the container since we are not trying to cause leaks.

Implementation in Rust

fn max_area(height: Vec<i32>) -> i32 {
    let mut maximum = 0;
    for i in 0..height.len() {
        for j in i+1..height.len() {
            let min_height = std::cmp::min(height[i], height[j]);
            let area = ((j-i) as i32) * min_height;
            maximum = std::cmp::max(maximum, area);
        }
    }
    maximum
}

Time Complexity: $O(n^2)$
Runtime on LeetCode: Time Limit Exceeded

Approach 2: Two Pointers

How does one move pointers in this case?
When you find that the height at left pointer is more than the height at right pointer, what do you do? You have the maximum height, so you try to find the second maximum, which is by moving the right pointer towards the left. Otherwise you just move the left pointer towards the right.

Pseudocode

initialize left, right = 0, n
while left < right
    compute area
    if height[left] > height[right]
        right -= 1
    else
        left += 1
    compute maximum
return maximum

Implementation in Rust

fn max_area_a2(height: Vec<i32>) -> i32 {
    let mut maximum = 0;
    let mut left_ptr = 0;
    let mut right_ptr = height.len() - 1;
    while left_ptr < right_ptr {
        let min_height = std::cmp::min(height[left_ptr], height[right_ptr]);
        let width = (right_ptr - left_ptr) as i32;
        let area = min_height * width;

        if height[left_ptr] > height[right_ptr] {
            right_ptr -= 1;
        } else {
            left_ptr += 1;
        }

        maximum = std::cmp::max(maximum, area);
    }
    maximum
}

Time Complexity: $O(n)$
Runtime on LeetCode: $10$ms