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 problem 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) {
    // Starting from the smallest height, find the farthest endpoint from the current one that is greater than or equal to its height (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, the 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 height of the shorter board multiplied by the width.

If you move the longer board, the width decreases, so the area becomes smaller. Therefore, we should always move the pointer of the shorter board, so that it is 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;
    }
};