Leetcode 11 - Container With Most Water

Link to problem

Description

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.

Solution

This problem could be solved easily with brute force (but you will get TLE). However, we could find a pattern when trying to brute force it.

From the example input: height = [1,8,6,2,5,4,8,3,7]:

• We check the container size with height[0]=1 as left and other values as right. Iterating from index 1 to 8, the size of the container would be: [1,2,3,4,5,6,7,8]. We found that the size of the container is always limited by the smaller vertical line.
• Therefore, if we try to move the smaller vertical line we are potentially getting a larger container!

From the above observation we could solve this problem with two pointers. Let the two pointers points to the start and end of the array heights. In each iteration, if the pointers does not meet, we shift the pointer with a smaller height left/right. At the same time we calculate the container size and keep the largest number.

If the heights we are comapring are equal…

It really does not matter which pointer we are moving.

• If one of the pointer now points to a larger height, the container size is still bounded by the smaller value. Moreover, our width is now one less. Therefore, the new container size must be smaller.
• If the new height is smaller than the preivous height. The container is smaller $\rightarrow$ not max area.

Implementation

class Solution {
public:
    int maxArea(vector<int>& height) {
        int i = 0, j = height.size() - 1;
        int output = 0;

        while (i < j) {
            int volume = (j - i) * min(height[i], height[j]);
            output = max(output, volume);

            (height[i] <= height[j])? i++: j--;
        }

        return output;
    }
};

impl Solution {
    pub fn max_area(height: Vec<i32>) -> i32 {
        let mut i = 0;
        let mut j = height.len() - 1;
        let mut output = 0;

        while i < j {
            let volume = (j - i) as i32 * std::cmp::min(height[i], height[j]);
            output = std::cmp::max(output, volume);

            if (height[i] <= height[j]) { i += 1; }
            else { j -= 1; }
        }

        output
    }
}