Backdrop Between Poles

Mediumtwo pointersAlso known as Container With Most Water

A photographer sets up in a park where a row of wooden poles stands exactly 1 metre apart. The poles have different heights. She wants to stretch one rectangular backdrop between two of the poles.

The backdrop is as wide as the distance between the two poles, and it can only be as tall as the shorter of the two, or it would sag. The poles in between do not get in the way: the backdrop hangs in front of them. Which two poles give the biggest backdrop?

Your task

Write widestBackdrop(heights). heights[i] is the height of pole i. For two poles i < j, the backdrop area is (j - i) × min(heights[i], heights[j]). Return the largest possible area.

If there are fewer than two poles, return 0.

widestBackdrop(heights: int[]) → int

Examples

Example 1

Input

heights = [3, 7, 2, 6, 4, 8, 1]

Output

Why

Poles 1 (height 7) and 5 (height 8) are 4 metres apart, and the shorter is 7, so the area is 4 × 7 = 28. The two ends give only 6 × 1 = 6, because pole 6 is so short.

Example 2

Input

heights = [2, 10, 9, 1]

Output

Why

The two tall neighbours, 10 and 9, give 1 × 9 = 9. Wider pairs are all held down by a short pole: 2 and 9 give 2 × 2 = 4, and 2 and 1 give 3 × 1 = 3.

Constraints

0 ≤ heights.length ≤ 10,000
0 ≤ heights[i] ≤ 10,000

Start with brute force

Try every pair of poles and compute its area. Keep the largest.

With 10,000 poles there are about 50 million pairs. Most of them are hopeless: a pair whose short pole has already been paired with something farther away can never win, and the brute force checks it anyway.

Hints

0 of 4 shown

Hint 1
Start with the widest pair, the two end poles, in [3, 7, 2, 6, 4, 8, 1]: area 6 × 1 = 6. The short pole on the right limits it. Could any other pair that uses that short pole do better?
Hint 2
Every other pair that uses the right-hand pole of height 1 is narrower and still at most 1 tall. So that pole can never beat 6, and you can throw it away.
Hint 3
That works in general: for the current pair of end poles, the shorter one has already had its best chance. Any other partner for it is closer, and the height is still capped by the short pole.
Hint 4
Put left at the first pole and right at the last. Record the area, then move whichever pointer is on the shorter pole one step inward. Repeat until they meet, keeping the largest area.

Walkthrough and solution

Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.

How to solve it

Start with the widest possible backdrop, the two end poles. Look at the shorter one. Any other partner for it is closer, and the height is still capped by that short pole, so it can never beat the area you just measured. You can drop it for good and move inward.

Trace [3, 7, 2, 6, 4, 8, 1]:

Poles 0 and 6 (3 and 1): 6 × 1 = 6. Best = 6. Pole 6 is shorter, so move right to 5.
Poles 0 and 5 (3 and 8): 5 × 3 = 15. Best = 15. Pole 0 is shorter, so move left to 1.
Poles 1 and 5 (7 and 8): 4 × 7 = 28. Best = 28. Move left to 2.
Poles 2 and 5 (2 and 8): 3 × 2 = 6. Move left to 3.
Poles 3 and 5 (6 and 8): 2 × 6 = 12. Move left to 4.
Poles 4 and 5 (4 and 8): 1 × 4 = 4. Move left to 5. The pointers meet. Answer: 28.

Six pairs measured instead of all 21. Moving the taller pole instead is the classic mistake: it throws away a pole that might still be part of the best pair.

Reference solution

function widestBackdrop(heights) {
  let left = 0, right = heights.length - 1;
  let best = 0;
  while (left < right) {
    const area = (right - left) * Math.min(heights[left], heights[right]);
    best = Math.max(best, area);
    // The shorter pole cannot do better with any closer partner.
    if (heights[left] < heights[right]) left++;
    else right--;
  }
  return best;
}

def widest_backdrop(heights):
    left, right = 0, len(heights) - 1
    best = 0
    while left < right:
        area = (right - left) * min(heights[left], heights[right])
        best = max(best, area)
        # The shorter pole cannot do better with any closer partner.
        if heights[left] < heights[right]:
            left += 1
        else:
            right -= 1
    return best

TimeO(n)Each step moves one pointer inward, so there are n - 1 steps.

SpaceO(1)Two pointers and the best area.

Learn the idea: Two Pointers Greedy Algorithms

Ctrl+Enter runs

Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.

Write code