Assign Pins to Shortest Columns
Company: Pinterest
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given a list of pins, where each pin has a height, and a fixed number of columns in a masonry-style layout.
Process the pins in their original order. For each pin, append it to the column whose current total height is the smallest. After appending the pin, that column's total height increases by the pin's height. If multiple columns have the same minimum height, choose the column with the smallest index.
Design and implement a function that returns the final assignment of pins to columns, or the final total height of each column. Also analyze the time and space complexity.
Example:
```text
heights = [5, 2, 4, 7, 1]
numColumns = 3
Initial column heights: [0, 0, 0]
Pin 5 -> column 0, heights become [5, 0, 0]
Pin 2 -> column 1, heights become [5, 2, 0]
Pin 4 -> column 2, heights become [5, 2, 4]
Pin 7 -> column 1, heights become [5, 9, 4]
Pin 1 -> column 2, heights become [5, 9, 5]
Final column heights: [5, 9, 5]
```
Quick Answer: This question evaluates understanding of greedy assignment strategies and data structures for maintaining and updating minimums in an online allocation problem, while also testing load-balancing reasoning and analysis of time and space complexity.
You are given a list of non-negative integers `heights`, where each value is the height of a pin, and a positive integer `numColumns`, the number of columns in a masonry-style layout. Process the pins in their original order. For each pin, place it into the column whose current total height is smallest. If multiple columns share the same minimum height, choose the column with the smallest index. In this problem, return the final total height of every column after all pins have been placed.
Constraints
- 1 <= numColumns <= 2 * 10^5
- 0 <= len(heights) <= 2 * 10^5
- 0 <= heights[i] <= 10^9
Examples
Input: ([5, 2, 4, 7, 1], 3)
Expected Output: [5, 9, 5]
Explanation: Pins are assigned in order to the current shortest column: 5->0, 2->1, 4->2, 7->1, 1->2. Final heights are [5, 9, 5].
Input: ([], 4)
Expected Output: [0, 0, 0, 0]
Explanation: With no pins to place, all columns remain at height 0.
Hints
- You need to repeatedly find the column with the smallest current total height, breaking ties by smaller index.
- A min-heap storing pairs like `(currentHeight, columnIndex)` lets you update the shortest column efficiently.