Move the Shorter Side: Greedy Pointer Moves
A row of poles stands one metre apart, with heights 3, 7, 2, 6, 4 and 8 metres. You will hang a rectangular banner between two of them. Its width is the distance between the poles, and its height is limited by the shorter pole, because the banner cannot hang higher than either support. Which two poles give the biggest banner? Checking all pairs works; one inward sweep is enough.
The rule
The shorter side caps the area, so move the shorter side.
Start with the two outermost poles: the widest banner possible. Every move inward costs one metre of width, so a move is only worth making if it could buy more height. Move the taller pole and the height is still capped by the shorter one, so the area can only shrink. Move the shorter pole and at least there is a chance of a taller partner.
def biggest_banner(heights):
left, right = 0, len(heights) - 1
best = 0
while left < right:
area = min(heights[left], heights[right]) * (right - left)
best = max(best, area)
if heights[left] < heights[right]:
left += 1 # the left pole is the cap: drop it
else:
right -= 1 # the right pole is the cap (or a tie): drop it
return bestWhy is dropping the shorter pole safe? Every pair it could still form uses a pole nearer to it, so the width is smaller, and the height can never exceed the short pole itself. None of those pairs can beat the area you just measured. The pole has been used up, and discarding it loses nothing. One sweep, n steps, constant memory.
The shortcut
This is the section's common thread: every move throws away something that has been proven useless. The both-ends check drops characters that already matched. The sorted squeeze drops a value that cannot reach the target with any partner. Here you drop the pole that caps the area. When you meet a new pair problem, look for the side you can prove is finished.
Positions 0 and 5
Height min(3, 8) = 3, width 5: area 15. The 3 is the cap, so move
left.
The trap is moving the taller pole "because it is bigger, so it has done its job". That is backwards: the taller pole is not the one limiting the banner.
Drills
Answer fast — trust the rule.
In poles [3, 7, 2, 6, 4, 8], what is the banner area between positions 1 and 3?
What does biggest_banner([5, 1, 1, 5]) return?
Why can moving the taller pole inward never produce a bigger banner?
Which of these problems does NOT suit converging pointers?
Remember
- The shorter side caps the area, so move the shorter side.
- Shortcut: every pointer move throws away something proven useless; find that side.
- Trap: moving the taller side, which cannot improve the answer.