Container With Most Water

Container With Most Water

What is this problem about?

The Container With Most Water interview question asks you to find two vertical lines in an array that, together with the x-axis, form a container that holds the most water. You are given an array of non-negative integers where each value represents the height of a line at that index. The goal is to maximize the area (width * min_height) between any two lines.

Why is this asked in interviews?

This is one of the most popular interview questions across all major tech companies, including Meta, Amazon, and Google. The Container With Most Water coding problem tests a candidate's ability to optimize a brute-force O(N^2) solution into a more efficient O(N) approach. It evaluates Greedy thinking and the ability to prove why a specific movement of pointers is correct.

Algorithmic pattern used

This problem follows the Array, Two Pointers, Greedy interview pattern.

1. Initialize two pointers: one at the start (left) and one at the end (right) of the array.
2. Calculate the current area: width = right - left, height = min(height[left], height[right]).
3. Update the global maximum area.
4. Greedy Step: Move the pointer pointing to the shorter line. This is because moving the taller line can only decrease the height (since it's capped by the shorter one) while definitely decreasing the width.

Example explanation

Heights: [1, 8, 6, 2, 5, 4, 8, 3, 7]

1. Left=0 (H=1), Right=8 (H=7). Area = 8 * 1 = 8. Move Left.
2. Left=1 (H=8), Right=8 (H=7). Area = 7 * 7 = 49. Move Right.
3. Left=1 (H=8), Right=7 (H=3). Area = 6 * 3 = 18. Move Right.
4. Left=1 (H=8), Right=6 (H=8). Area = 5 * 8 = 40. (Any choice). The maximum area found is 49.

Common mistakes candidates make

• Brute Force: Using nested loops to check every pair, which results in a Time Limit Exceeded error for large arrays.
• Moving both pointers: Forgetting that you only need to move one pointer at a time to explore all potential maxima.
• Incorrect height logic: Using the average height or the taller line instead of the shorter line to calculate the area.

Interview preparation tip

Practice explaining the proof for moving the shorter pointer. Showing that moving the taller pointer cannot result in a larger area is often the key to getting a high score in the interview.