SimuVedaAlgorithms Lab Open in the lab

Patterns / Intermediate

Container with Most Water Visualizer

Start with the widest container. Always move the shorter wall inward, because the taller wall can never do better with less width.

Start the Container with Most Water simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(n)
Average timeO(n)
Worst timeO(n)
Extra spaceO(1)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Walls at both ends. Area = shorter wall × distance between them. [1, 8, 6, 2, 5, 4, 8, 3, 7]
  2. min(1, 7) × 8 = 8. New best.
  3. The left wall (1) is shorter, so move l inward.
  4. min(8, 7) × 7 = 49. New best.
  5. The right wall (7) is shorter or equal, so move r inward.
  6. min(8, 3) × 6 = 18.
  7. The right wall (3) is shorter or equal, so move r inward.
  8. min(8, 8) × 5 = 40.
  9. The right wall (8) is shorter or equal, so move r inward.
  10. min(8, 4) × 4 = 16.
  11. The right wall (4) is shorter or equal, so move r inward.
  12. min(8, 5) × 3 = 15.
  13. The right wall (5) is shorter or equal, so move r inward.
  14. min(8, 2) × 2 = 4.
  15. The right wall (2) is shorter or equal, so move r inward.
  16. min(8, 6) × 1 = 6.
  17. The right wall (6) is shorter or equal, so move r inward.
  18. Done. The most water is 49, between index 1 and 8.

Try it with your own input →

Container with most water in Java, Python, C++, C and JavaScript

int maxArea(int[] h) {
  int l = 0, r = h.length - 1, best = 0;
  while (l < r) {
    int area = Math.min(h[l], h[r]) * (r - l);
    best = Math.max(best, area);
    if (h[l] < h[r]) l++;
    else r--;
  }
  return best;
}
def max_area(h):
    l, r, best = 0, len(h) - 1, 0
    while l < r:
        area = min(h[l], h[r]) * (r - l)
        best = max(best, area)
        if h[l] < h[r]:
            l += 1
        else:
            r -= 1
    return best
int maxArea(const vector<int>& h) {
  int l = 0, r = (int)h.size() - 1, best = 0;
  while (l < r) {
    int area = min(h[l], h[r]) * (r - l);
    best = max(best, area);
    if (h[l] < h[r]) l++;
    else r--;
  }
  return best;
}
int maxArea(int h[], int n) {
  int l = 0, r = n - 1, best = 0;
  while (l < r) {
    int area = (h[l] < h[r] ? h[l] : h[r]) * (r - l);
    if (area > best) best = area;
    if (h[l] < h[r]) l++;
    else r--;
  }
  return best;
}
function maxArea(h) {
  let l = 0, r = h.length - 1, best = 0;
  while (l < r) {
    const area = Math.min(h[l], h[r]) * (r - l);
    best = Math.max(best, area);
    if (h[l] < h[r]) l++;
    else r--;
  }
  return best;
}

In an interview

LeetCode 11, Container With Most Water: pick two walls that hold the most water.

The interviewer will ask you to prove the greedy move is safe. The argument in the idea above is the proof.

More patterns