Sum of Areas of Rectangles from an Array

Sum of Areas of Rectangles hands you a bag of stick lengths and asks you to glue them into rectangles so the total area is as large as possible. The winning move is a classic greedy one: sort the sticks, then pair the biggest ones together first.

The slow way first

You could try every way of grouping the sticks into pairs and add up each grouping's area, keeping the best. The number of pairings explodes factorially — utterly hopeless for more than a handful of sticks.

The question to ask: which sticks should sit together? If a long stick is paired with a short one, the short one caps the rectangle and the long one's length is wasted. So we want long sticks paired with long sticks.

The idea: sort, then pair neighbours

Sort the sticks descending. Now the two longest are next to each other, then the next two, and so on. Walk the sorted array two at a time: each adjacent pair (sides[i], sides[i+1]) becomes one rectangle, and we add sides[i] * sides[i + 1] to a running total.

Because equal-or-near-equal neighbours are paired, big sticks never get crippled by tiny ones. That neighbour-pairing on a sorted array is exactly what makes the greedy choice optimal.

Walk through it

Step through the animation. The array is already sorted to [5, 5, 4, 3, 3, 2]. The pointer i jumps two cells at a time. Each pair lights up, its rectangle area is computed, and the area label grows: 25, then 37, then 43.

Pseudocode

sort sides from largest to smallest
area = 0
i = 0
while there are still two sticks left (i + 1 < n):
    length = sides[i]
    width  = sides[i + 1]
    area = area + length * width      # this pair forms one rectangle
    i = i + 2                          # consume both sticks
return area

The Python solution

def sum_of_areas(sides):
    sides.sort(reverse=True)
    area = i = 0
    while i + 1 < len(sides):
        length = sides[i]
        width = sides[i + 1]
        area += length * width
        i += 2
    return area

• sides.sort(reverse=True) puts the longest sticks first so neighbours are the closest in length.
• area = i = 0 starts the running total and the index at zero.
• The while guard i + 1 < len(sides) keeps going as long as a full pair remains.
• length and width are just the two neighbouring sticks at i and i + 1.
• area += length * width adds this rectangle's area to the total.
• i += 2 consumes both sticks and moves to the next untouched pair.

Complexity

The sort costs O(n log n) and the single sweep is O(n), so sorting dominates. Beyond the sort we use only a couple of variables, so the extra space is O(1).

When this pattern shows up

Practice