Solving the 'Container With Most Water' on LeetCode with C++

Problem

https://leetcode.com/problems/container-with-most-water/description/

Answer

class Solution {
public:
    int maxArea(vector<int>& height) {
        int maxArea = 0;
        int left = 0;
        int right = height.size() - 1;

        while (left < right) {
            int h = min(height[left], height[right]);
            int w = right - left;
            maxArea = max(maxArea, h * w);

            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }

        return maxArea;
    }
};

Let's consider a solution to this problem.

We want to find a container that can hold the most water. This is calculated as the maximum value derived from multiplying the height and width (between two bars).

How do we find the height and width?

The maximum width (distance between two bars) is between the first and last bars.

For example, in the array [3, 2, 4, 2, 5], the first bar (index 0) and the last bar (index 4) offer the maximum width.

So we begin finding a container with the most water from both ends.

We then move to the next index. However, we are unsure which index to move to.

We move the index with the smaller height to the next one. This is because we aim to find a container with the most water, hence we should continue selecting a taller height.

For example, in the array [3, 2, 4, 2, 5], the first bar (index 0) and last bar (index 4) provide the maximum width. The container size is 12 (height 3 * width 4), and the height used is determined by the shorter bar.

Then, the indices are 1 (height 2) and 4 (height 5) because we should continue to select a taller height. The container size is 6 (height 2 * width 3).

The next indices are 2 (height 4) and 4 (height 5). The container size is 8 (height 4 * width 2).

The final indices are 3 (height 2) and 4 (height 5). The container size is 2 (height 2 * width 1).

The container that holds the most water has a size of 12 (when indices are 0 and 4).

We converts the above algorithm to code.
I repost the answer code.

class Solution {
public:
    int maxArea(vector<int>& height) {
        int maxArea = 0;
        int left = 0;
        int right = height.size() - 1;

        while (left < right) {
            int h = min(height[left], height[right]);
            int w = right - left;
            maxArea = max(maxArea, h * w);

            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }

        return maxArea;
    }
};

        int maxArea = 0;
        int left = 0;
        int right = height.size() - 1;

The code starts from the first and last indices because the width is at its maximum.

        while (left < right) {

        }

We continue comparing containers until the left index is less than or equal to the right index.

        while (left < right) {
            int h = min(height[left], height[right]);
            int w = right - left;
            maxArea = max(maxArea, h * w);

The 'h' variable takes the smaller height from the left or right index, because the container height is determined by the shorter bar.

The 'w' variable is obtained by subtracting the left index from the right one.

The 'maxArea' variable stores the larger area between the old and the new one.

            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }

After calculating the area from the height and width, we move the index that has the smaller height because a larger height could yield a larger area.

That's all.