Your question is Pinterest Waterfall Layout Implementation. Start with the requirements on the right.
Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.
Pinterest displays Pins in a waterfall layout by placing each rectangle, in feed order, into the currently shortest column. Implement this placement algorithm and return each rectangle's assigned column and vertical offset.
Use a min-heap ordered by (current_column_height, column_index). The column index breaks ties, so the leftmost shortest column is always selected. After placing a rectangle, increase that column's height by rectangle_length + gap.
Implement waterfall_layout(lengths, column_count, gap). lengths is an array of positive integers representing Pin rectangle heights. column_count and gap are nonnegative integers. Return an array where result i is [column_index, top], indicating the column and vertical coordinate of rectangle i. The first row starts at vertical coordinate 0.
Rectangles must remain in their original order. Do not sort lengths.
def waterfall_layout(lengths, column_count, gap):