Skip to content

The Widest Reservoir

Jump to bottom
Andrew Burke edited this page Aug 19, 2026 · 1 revision

TIP103 Unit 11 Session 1 (Click for link to problem statements)

The Widest Reservoir

A row of vertical walls has heights given by heights, where wall i stands at position i. Choosing two walls forms a container whose water capacity is the shorter wall's height times the distance between them.

Return the maximum amount of water any pair of walls can hold.

def max_area(heights):
    pass

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 20-30 mins
  • 🛠️ Topics: Arrays, Two Pointers, Greedy

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?

  • Q: How is the capacity of a pair of walls calculated?

    • A: Capacity = min(heights[i], heights[j]) * (j - i). The water level cannot rise above the shorter wall, and the width is the distance between the two positions.

  • Q: Do the walls between the chosen pair affect the capacity?

    • A: No. Only the two chosen walls matter; any walls between them are ignored (the water sits above them).

  • Q: Can the container be tilted, or can we use more than two walls?

    • A: No. Exactly two walls are chosen, and the capacity formula above is the only rule.
HAPPY CASE
Input: heights = [1, 8, 6, 2, 5, 4, 8, 3, 7]
Output: 49
Explanation: Walls at positions 1 and 8 have heights 8 and 7. Capacity = min(8, 7) * (8 - 1) = 7 * 7 = 49, the maximum over all pairs.

EDGE CASE
Input: heights = [1, 1]
Output: 1
Explanation: Only one pair exists. Capacity = min(1, 1) * 1 = 1.

Input: heights = [1, 2, 1]
Output: 2
Explanation: The tallest wall alone holds nothing; the best pair is the two outer walls: min(1, 1) * 2 = 2.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Maximizing over Pairs in an Array, we can consider the following approaches:

  • Two Pointers: Start with the widest possible container (leftmost and rightmost walls) and greedily shrink inward from the shorter side, since moving the taller wall inward can never increase the capacity.
  • Brute Force: Check every pair of walls in O(N^2). Correct, but too slow for large inputs and a signal to look for the two-pointer optimization.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:
Place one pointer at each end of the array so we begin with the maximum width. At each step, record the capacity of the current pair, then move the pointer at the shorter wall inward. Moving the shorter wall is the only move that can possibly find a larger capacity: the width always shrinks, so the only hope is a taller limiting wall. Repeat until the pointers meet, tracking the best capacity seen.

1) Initialize `left = 0`, `right = len(heights) - 1`, and `best = 0`.
2) While `left < right`:
   a) Compute capacity = min(heights[left], heights[right]) * (right - left).
   b) Update `best` if this capacity is larger.
   c) If heights[left] < heights[right], move `left` inward by 1.
      Otherwise, move `right` inward by 1.
3) Return `best`.

⚠️ Common Mistakes

  • Moving the pointer at the taller wall — the shorter wall is the bottleneck, so keeping it can never improve the capacity as the width shrinks.
  • Using the taller wall's height (or the sum/average) in the capacity formula instead of the shorter wall's height.
  • Returning the capacity of the first or last pair checked instead of tracking the maximum across all steps.

4: I-mplement

Implement the code to solve the algorithm.

def max_area(heights):
    left, right = 0, len(heights) - 1
    best = 0

    while left < right:
        # Capacity is limited by the shorter wall times the distance between walls
        width = right - left
        capacity = min(heights[left], heights[right]) * width
        best = max(best, capacity)

        # Move the pointer at the shorter wall inward; moving the taller
        # one can never increase the capacity
        if heights[left] < heights[right]:
            left += 1
        else:
            right -= 1

    return best

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

  • Input: heights = [1, 8, 6, 2, 5, 4, 8, 3, 7]

    • left = 0 (h=1), right = 8 (h=7): capacity = 1 * 8 = 8, best = 8. Left wall is shorter, so left moves to 1.
    • left = 1 (h=8), right = 8 (h=7): capacity = 7 * 7 = 49, best = 49. Right wall is shorter, so right moves to 7.
    • The pointers continue inward (capacities 18, 40, 16, 15, 4, 6) but nothing beats 49.
    • Output: 49

  • Input: heights = [1, 1]

    • left = 0 (h=1), right = 1 (h=1): capacity = 1 * 1 = 1, best = 1. Pointers meet and the loop ends.
    • Output: 1

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the number of walls in heights.

  • Time Complexity: O(N) because each step moves one pointer inward, so the pointers together make at most N - 1 moves before meeting.
  • Space Complexity: O(1) because we only store the two pointers and the running maximum.

Clone this wiki locally