Container With Most Water

Problem

You are given an integer array heights where heights[i] represents the height of the ithith bar.

You may choose any two bars to form a container. Return the maximum amount of water a container can store.

Examples

Example 1:

Input: height = [1,7,2,5,4,7,3,6]

Output: 36

Example 2:

Input: height = [2,2,2]

Output: 4

Constraints

• 2 <= height.length <= 1000
• 0 <= height[i] <= 1000

You should aim for a solution with O(n) time and O(1) space, where n is the size of the input array.

Solution

Start by considering the entire volume. We will then move the left and right sides inward. For each step, compute the width, height (min of the two ends) and area. Check for a new best. Then move the left or right side inwards, which ever is the smaller of the two.

class Solution {
public:
    int maxArea(vector<int>& heights) {
        std::size_t left = 0;
        std::size_t right = heights.size() - 1;
        int max_area = 0;
        while (left < right) {
            const auto width = right - left;
            const auto height = std::min(heights[left], heights[right]);
            auto area = static_cast<int>(width * height);
            max_area = std::max(area, max_area);
            heights[left] < heights[right] ? ++left : --right;
        }
        return max_area;
    }
};