Masonry layout
Place cards of different heights into columns by always putting the next card in the shortest column.
O(n * k)Space O(n + k)3 practice problemsStep-through pictureThe idea
A masonry layout shows cards of different heights in columns with no big gaps, like the boards on Pinterest. Cards keep their order roughly left to right, top to bottom, but each column's stack is as tight as possible.
The rule is greedy: keep the current height of every column in columnHeights. For each card, find the shortest column, place the card at the bottom of that column, and add the card's height (plus the gap) to it. When two columns are equally short, pick the leftmost one so the result is predictable.
A plain CSS grid can't do this on its own, because grid rows line up across columns, which leaves gaps under short cards. That is why masonry is usually done in JavaScript, by measuring cards and setting their positions.
An everyday example
Stacking boxes into delivery vans
Boxes come off a belt one at a time, and you have three vans that are loaded from the bottom up. To keep the loads even, each new box goes into the van with the lowest stack. If two vans are equally low, you use the one nearest to you. You write down which van each box went into and how high up it sits.
| In the example | In the code |
|---|---|
| The vans | The columns, 0 to columnCount - 1 |
| How high each van's stack is | columnHeights[c] |
| Finding the lowest stack, nearest first | The loop that keeps shortest, using < so ties keep the left column |
| Writing down where the box went | placements.push({ column: shortest, top: ... }) |
From the slow way to masonry layout
- Start with the obvious layouts. A CSS grid puts cards in rows, and each row is as tall as its tallest card, so short cards leave holes under them. Putting card
iin columni % kremoves the holes, but the columns end at very different heights: one tall card early can make its column run far longer than the rest. - The perfect answer would split the cards so the tallest column is as short as possible. That is a scheduling problem known to be NP-hard: no fast exact method is known, and it would also reorder the cards, which breaks the reading order users expect.
- So place cards one at a time, in order, and ask a smaller question: where should this one card go to keep things even? The column with the least content is where the biggest hole is. Putting the card anywhere else makes a tall column taller and leaves the hole.
- Keep
columnHeights, scan it for the smallest value, and keep the leftmost column on ties by using<. The card'stopis that column's height, and the column grows by the card's height plusgap. That greedy loop is masonry layout.
How it works
- Make
columnHeights, one0for each column, and an empty listplacements. - For each card's
height, findshortest: start with column0and switch to columnconly if it is strictly shorter. - The card's top is the shortest column's current height. Record
{ column: shortest, top }. - Grow that column:
columnHeights[shortest] += height + gap. - After all cards,
placementssays where each card goes. The container's height is the tallest column, minus the lastgap.
Watch it run
This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.
See every step at onceThe same run, laid out side by side
The code
Point at a note to light up the lines it explains.
function masonry(heights, columnCount, gap) {const columnHeights = new Array(columnCount).fill(0);const placements = [];for (const height of heights) {let shortest = 0;for (let c = 1; c < columnCount; c++) {if (columnHeights[c] < columnHeights[shortest]) shortest = c;}placements.push({ column: shortest, top: columnHeights[shortest] });columnHeights[shortest] += height + gap;}return placements;}
How fast it is
| Time | O(n * k) |
|---|---|
| Extra memory | O(n + k) |
For each of n cards, all k columns are checked. The placements list has one entry per card, and the heights list one per column.
- Best case
O(n)One column: the inner loop never runs, and each card just goes on top of the last.
- Average case
O(n * k)Every one of the
ncards scans allkcolumns, whatever their heights. - Worst case
O(n * k)Same scan, with many columns, like a wide wall of 12 columns: 12 checks per card.
Common mistakes
- Using
<=when choosing the shortest column. Ties then go to the rightmost column, and the first row fills from the right. - Forgetting the gap, or adding it before the first card. Each card adds its height plus one gap; the container's height subtracts the final gap.
- Placing cards before their images load. The heights are wrong, so cards overlap once images appear. Measure after load, or reserve space with known aspect ratios.
- Recomputing the layout from scratch on every scroll. The layout only changes when cards or column count change.
When to use it
Look for these clues in a problem:
- Items of different heights must be spread across a fixed number of columns.
- Each item goes to the column, worker, or lane that is currently least loaded.
- The question asks for each item's column and top position, or the final total height.
- Ties between equal columns must be broken by a rule like "leftmost first".
Check yourself
Answer each one in your head first, then open it.
Why does the code use < and not <= to find the shortest column?
With <, a later column only wins if it is strictly shorter, so ties keep the leftmost column. With <=, ties would go to the rightmost column and the first row would fill from the right.
How tall is the container in the trace, and why subtract a gap?
230. The tallest column is 240, but that includes a gap after its last card, which isn't needed at the bottom of the container.
When every card has a positive height, which columns do the first k cards go to?
Columns 0 to k - 1, in order, all at top 0. The columns tie at 0, so each card takes the leftmost column that is still empty.
Can the greedy layout ever be more than twice as tall as the best one?
No. The card that ends lowest started no lower than the average column height, and it is no taller than the best layout's tallest column, so the total is at most twice the best.
Practice problems
Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.
0 of 3 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.
Start practicingGo further
You don't need these to start practicing. Open one when you want more.
Why it works
The reasoning that makes it always right
Cards never overlap, because of one rule: columnHeights[c] is always the bottom of the last card in column c plus one gap. Each new card starts at that value, and the column grows by exactly the card's height plus gap, so the rule stays true.
The columns stay even, because of a second rule: the tallest column is never more than the tallest card so far, plus gap, above the shortest. It's true at the start, when all are 0. Adding to the shortest column makes it at most the old shortest plus one card plus gap, and the shortest can only go up. So the difference never grows past one card and one gap.
Greedy isn't perfect, but it's never far off. Look at the card that ends lowest. When it was placed, its column was the shortest, so it started no lower than the average column height, and the best possible layout's tallest column is at least that average. The card itself is no taller than the best layout's tallest column. So the greedy layout is never more than twice as tall as the best one. This is the classic bound for list scheduling.
Going deeper
3 more ideas
Why always picking the shortest column keeps things even
Putting a card on the shortest column can never make the gap between the tallest and shortest column larger than the tallest card plus a gap. Any other choice would stack onto a taller column and leave the short one emptier. The result isn't always the best possible packing, but it is fast, keeps reading order sensible, and looks balanced.
How fast it is
Scanning all k columns for every one of n cards is O(n * k). With a few columns that is tiny. For many columns, keep the columns in a min-heap ordered by height and then by column index, which makes each placement O(log k).
Shortest column versus strict order
Some masonry layouts place cards strictly in column order, card i in column i % k. That keeps the order perfectly but leaves uneven bottoms. The shortest-column rule trades a little order for a much tidier layout.
Work it by hand
Every step in a table, with why
Place 7 cards into 3 columns with a gap of 10. Ties at the start fill left to right, and column 2 takes two cards in a row.
heights = [90, 150, 60, 60, 120, 45, 70], columnCount = 3, gap = 10
| Step | height | columnHeights before | shortest | top | columnHeights after | Why |
|---|---|---|---|---|---|---|
| 1 | 90 | [0, 0, 0] | 0 | 0 | [100, 0, 0] | All three columns are at 0. < never switches on a tie, so column 0 wins. |
| 2 | 150 | [100, 0, 0] | 1 | 0 | [100, 160, 0] | Columns 1 and 2 tie at 0. Column 1 is checked first and column 2 isn't strictly shorter, so column 1 wins. |
| 3 | 60 | [100, 160, 0] | 2 | 0 | [100, 160, 70] | Column 2 is still empty. |
| 4 | 60 | [100, 160, 70] | 2 | 70 | [100, 160, 140] | Column 2 is still the shortest at 70, so it takes another card. A plain i % 3 layout would have put this card in column 0. |
| 5 | 120 | [100, 160, 140] | 0 | 100 | [230, 160, 140] | Now column 0 at 100 is the shortest. |
| 6 | 45 | [230, 160, 140] | 2 | 140 | [230, 160, 195] | Column 2 at 140 is shortest again. |
| 7 | 70 | [230, 160, 195] | 1 | 160 | [230, 240, 195] | Column 1 at 160 takes the last card. All 7 cards are placed, so the loop ends. |
The container is 240 - 10 = 230 pixels tall: the tallest column minus its last gap. Placing card i in column i % 3 would give 280. The best possible split of these cards, ignoring order, gives 220.
Compared with other ways
When to pick something else
| Approach | Time | Extra memory | Choose it when |
|---|---|---|---|
| Masonry layout | O(n * k) | O(n + k) | A card wall with a handful of columns. It keeps rough reading order and even bottoms with very little code. |
| Masonry with a min-heap | O(n log k) | O(n + k) | Many columns, or the same rule used for many workers or lanes, where scanning all of them for every card adds up. |
Strict column order (i % k) | O(n) | O(n) | Reading order matters more than even bottoms, or you need to know a card's column before measuring anything. |
| Trying every split for the best packing | O(2^n) | O(n) | Practically never: with 2 columns there are 2^n ways to split the cards, more with more columns, and it ignores reading order. |
Extra memory: O(n + k): one placement per card and one height per column.
How the steps grow
- Masonry layout
O(n * k) - Masonry with a min-heap
O(n log k) - Strict column order (
i % k)O(n) - Trying every split for the best packing
O(2^n)
| Approach | n = 10 | n = 1,000 | n = 1,000,000 |
|---|---|---|---|
| Masonry layout | 100 | 1 million | 1 trillion |
| Masonry with a min-heap | 33 | 9,966 | 20 million |
Strict column order (i % k) | 10 | 1,000 | 1 million |
| Trying every split for the best packing | 1,024 | more than a quadrillion | more than a quadrillion |
Inputs that need care
5 tricky inputs
- One column:
columnCount = 1 - The inner loop doesn't run,
shortestis always 0, and cards stack in order: tops0, thenh0 + gap, and so on. - More columns than cards:
[10, 20]in 5 columns - Each card goes to the next empty column at top 0: columns 0 and 1. Columns 2 to 4 stay empty, so you may want to center the used columns.
columnCount = 0columnHeightsis empty,shorteststays 0, andcolumnHeights[0]isundefined, sotopisundefinedand later values becomeNaN. Guard against it withMath.max(1, columnCount).- Every card has height 0:
[0, 0, 0]in 2 columns,gap = 8 - The gap still grows each column, so the cards go to columns 0, 1, 0 at tops 0, 0, 8. Equal cards fill round-robin, left to right.
- Images that haven't loaded yet
- Their measured height is too small, so later cards overlap them once they load. Use the known width and the image's aspect ratio to compute the height before it loads, or lay out again after loading.
Variations and follow-ups
Twists interviewers add
A min-heap of columns
Keep the columns in a min-heap ordered by height and then by column index. Taking the shortest is O(1) and putting it back is O(log k), so the whole layout is O(n log k). It only matters with many columns.
Strict column order
Card i goes in column i % k. Reading order is perfectly predictable, but the bottoms are uneven: 280 instead of 230 in the trace.
Cards that span two columns
For a card as wide as two columns, try each pair of side-by-side columns and pick the pair where the taller of the two is lowest. The card's top is that taller height, and both columns grow to the card's bottom plus gap.
Justified rows
Photo galleries often use rows instead: every image in a row is scaled to the same height so the row fills the width exactly. That is a line-breaking problem, like wrapping words in a paragraph, not a shortest-column one.
In an interview
Spot it, explain it, answer follow-ups
- Spot it from "shortest column", "least loaded", "assign each item to the lane with the least work", or a request for each card's column and top.
- Explain the greedy rule and the tie rule in one sentence each. Then mention the cost,
O(n * k), and that a min-heap makes itO(n log k). - Test by hand: all columns tied at the start, one column, more columns than cards, and a tall first card that should make later cards avoid its column.
- Expect the follow-up "is this the best possible layout?". Answer: no, finding the best split is NP-hard, but greedy is never more than twice the best height, and in practice it is close, like 230 against 220 in the trace.
Where frontend code uses it
The same idea in real UI code
- Pinterest-style boards, photo galleries, and dashboard card walls place each card in the shortest column.
- Libraries like Masonry (by David DeSandro) and many React masonry components measure cards and set their positions with this rule.
- CSS is adding native masonry layout (the masonry value for grid, under discussion and behind flags in some browsers), which uses the same shortest-track idea.