How to Perfect a Waterfall Layout: A Frontend Engineer’s Algorithmic Journey

Introducing the Album Feature

Yuque’s album function lets users showcase photos, food, travel moments, and more, but the initial version suffered from uneven column heights.

Development Story

Can the Waterfall Layout Be Neater?

The classic waterfall layout distributes each new image to the shortest column, a greedy algorithm that works well in many cases but breaks when the last image is tall, causing visual imbalance.

The greedy approach is essentially a greedy algorithm that places each image in the column with the current minimum height.

Because Yuque’s editor knows each image’s width and height beforehand, we can compute a globally optimal arrangement instead of relying on incremental greedy placement.

We abstract the problem as:

Split a numeric array into n groups so that each group’s sum is as close as possible to the others

, a classic NP‑hard partitioning problem.

Analysis

ChatGPT could not provide a reliable solution, so we consulted a colleague who described the task as a load‑balancing problem with NP‑hard complexity, meaning only approximate solutions are feasible.

Proposed Solution

Compute the average sum and aim for each group’s total to approach this average. Sort the original array in descending order to reduce search complexity. Iterate through the sorted array, adding numbers to the current group until adding the next number would exceed the average; then compare the overshoot with the previous number and choose the closer one. For the final group, assign remaining numbers without reference to the average, ensuring all items are placed.

Mark already‑assigned items to avoid duplicate grouping.

Image‑Specific Adjustments

Pure mathematical optimality must be tempered by visual considerations. For example, placing all long images in one column creates a “staggered” look that feels unbalanced.

Staggered Effect

Sorting first and then distributing can cause long images to cluster, so we compromise by initially distributing the first n largest images across the n columns to spread height more evenly.

We also preserve the original image order as much as possible by re‑ordering within each column after grouping.

Re‑order images inside each column according to their original sequence. Re‑order columns themselves based on the first image’s original position.

Current Version Pros and Cons

The present implementation achieves a better balance than the pure greedy method, though it remains an approximation and may still struggle with extreme size disparities or large image sets. It also slightly distorts the original order, which can be mitigated by user adjustments.

Future Work: Puzzle Layout

We plan to introduce a “puzzle” layout that keeps original image proportions, allows free placement, and automatically assembles a tidy rectangle, a more complex problem than the current waterfall approach.

Fundamental Knowledge

P, NP, NP‑complete, and NP‑hard problems: link

Dynamic programming basics: link

Complexities are divided into polynomial‑time (e.g., O(n), O(log n), O(n²)) and non‑polynomial‑time (e.g., O(aⁿ), O(n!)) categories.

While ChatGPT can speed up brainstorming, its answers must be verified, especially for algorithmic correctness.

Follow us for updates on the upcoming puzzle feature.