Container With Most Water

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 $i^{th}$ 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.

Intuition

The area of water a container is determined by two factors:

  1. height: limited by the shorter of the two lines
  2. width: the distance between two vertical lines

Formula: area = width * min(height[left], height[right])

two pointer approach:

  1. Start with the widest container (left = 0, right = n-1), which gives us maximum width
  2. Calculate the current area and update the maximum
  3. To potentially find a larger area, we need to move the pointers inward.
    Moving the pointer at the shorter line might increase the height, which could compensate for the reduced width → potential for larger area
  4. Repeat until the two pointers meet

Algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int maxArea(vector<int>& height) {
        int ret = 0;

        int n = height.size();

        int left = 0;
        int right = n - 1;
        while(left < right) {
            int area = (left - right) * min(height[left], height[right]);
            rat = max(rat, area);
            
            if (height[left] > height[right]){
                right--;
            }
            else{
                left++;
            }
        }
        return rat;
    }
};