Two Boards Holding Water

Medium

Vertical boards are driven into the ground along a line at equal spacing: board i stands at position i and has height heights[i]. Pick two boards; together with the ground they form a tank. Water fills it up to the height of the shorter board, and the tank's width is the distance between the two boards. Any boards standing between them do not affect the volume. Return the largest amount of water (height × width) that two boards can hold.

Example 1

heights=[3, 9, 2, 4, 7, 1] → 21

Take the boards at indices 1 and 4: the water level is limited by the shorter one (7) and they are 3 apart, so 7 · 3 = 21.

Example 2

heights=[5, 0, 0, 5] → 15

The two outer boards of height 5 are 3 apart, giving 15. The zero-height boards in between do not get in the way.

Example 3

heights=[6, 2] → 2

Constraints

2 ≤ len(heights) ≤ 10⁵
0 ≤ heights[i] ≤ 10⁴

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array Two Pointers

Similar problems

Studios for Recording Sessions Medium Fix the Middle of the Line Medium Stick Triples That Form a Triangle Medium Best-Paid Gig for Each Worker Medium Lining Up Against Rivals Medium

Input

heights=[3, 9, 2, 4, 7, 1]

Expected

Run checks the first 3 tests in your browser. Submit checks all 119 tests on the server, hidden ones included.