Interview Classic 150 Questions P11 Container With Most Water

---

Timeline

Timeline

2025-10-04

init

Two pointers

---

Problem:

P11 Container With Most Water

https://leetcode.cn/problems/container-with-most-water/description/?envType=daily-question&envId=2025-10-04

This is a classic two-pointer problem, but my initial solution did not use two pointers; instead, it was based on the following fact:
If one endpoint forms one side of the container, then the other endpoint that forms the container with the most water is the one farthest from it and with a height greater than or equal to its height.

#include <vector>

using std::vector;

class Solution {
public:
  int maxArea(vector<int> &height) {
    // Start from the smallest height, and for the current endpoint, find the farthest endpoint with height greater than or equal to it (search both left and right).
    int n, i, j;
    int max = -1;
    int curr_height;
    n = height.size();

    for (i = 0; i < n; i++) {
      curr_height = height[i];
      for (j = n - 1; j > i; j--) {
        if (height[j] >= curr_height) {
          max = std::max(max, curr_height * (j - i));
          break;
        }
      }
      for (j = 0; j < i; j++) {
        if (height[j] >= curr_height) {
          max = std::max(max, curr_height * (i-j));
          break;
        }
      }
    }
    return max;
  }
};

Although the above solution optimizes the brute-force double loop, its worst-case time complexity is still O(n^2), which is not as efficient as the two-pointer approach:

• The area is determined by the shorter height × width.

If we move the longer board, the width decreases, so the area will become smaller. Therefore, we should always move the shorter board pointer, which makes it possible to find a larger area.

Time complexity O(n).

#include <vector>
#include <algorithm>
using std::vector;

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

        while (left < right) {
            int h = std::min(height[left], height[right]);
            int w = right - left;

            max_area = std::max(max_area, h * w);

            // Move the shorter board
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return max_area;
    }
};