Two Pointers Pointers from both ends
155. Container With Most Water
You are given an array heights that describes a row of thin walls standing one unit apart. Wall i stands
at position i and is heights[i] units tall.
Choose two of the walls and take all the other walls away. Then pour water into the space between the two walls you kept. The water rises until it reaches the top of the shorter wall, so the amount it holds is the distance between the two walls times the height of the shorter one. Return the largest amount of water that any choice of two walls can hold.
Here are the walls of Example 1, and the water that walls 1 and 4 hold when you keep only those two. The water is 3 units wide and 7 units high, so it holds 21 units. It spills over the wall of height 7 before it can reach the top of the wall of height 8.
Example 1
Input: heights = [3, 7, 2, 5, 8, 1, 6, 2]
30Explanation: Keep walls 1 and 6, of heights 7 and 6. The water is 5 units wide and 6 units high, so it holds 30. The two tallest walls, 1 and 4, hold only 21.
Example 2
Input: heights = [0, 5, 0, 0, 5, 0]
15Explanation: Walls 1 and 4 are 3 apart and both 5 tall, so they hold 3 × 5 = 15. A wall of height 0 holds no water, so every pair that uses one holds 0.
Example 3
Input: heights = [4, 10, 10, 4]
12Explanation: The two outer walls are short but far apart, and they hold 3 × 4 = 12. The two walls of height 10 are neighbours, so they hold only 1 × 10 = 10.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
2 ≤ heights.length ≤ 1050 ≤ heights[i] ≤ 109
Clarifying questions
What you would ask an interviewer before writing any code.