FastPrep
Problem · Heap

Assign Pins to the Shortest Column

● MediumPinterestFULLTIMEPHONE SCREEN

You are given an array pins, where pins[i] is the height of the ith pin. There are k columns, and each column starts with total height 0.

Process the pins in their original order. For each pin, append it to the column with the smallest current total height. If multiple columns are tied for the smallest height, choose the column with the smallest index. After appending a pin, that column's total height increases by the pin's height.

Return a two-row matrix:

  • The first row contains the assigned column index for each pin.
  • The second row contains the final total height of each column.
Examples
01 · Example 1
pins = [1,2,3,4,5]
k = 2
return = [[0,1,0,1,0],[9,6]]

The assigned columns are [0,1,0,1,0]. Final heights are 9 and 6.

02 · Example 2
pins = [10,20,30]
k = 3
return = [[0,1,2],[10,20,30]]
03 · Example 3
pins = [5,5,5,5,5,5]
k = 2
return = [[0,1,0,1,0,1],[15,15]]
Constraints
  • 1 <= k <= pins.length
  • 1 <= pins.length <= 2 * 10^5
  • 1 <= pins[i] <= 10^9
  • Use a min-heap or equivalent data structure for efficient assignment.
More Pinterest problems
drafts saved locally
public int[][] assignPinsToColumns(int[] pins, int k) {
    // write your code here
}
pins[1,2,3,4,5]
k2
expected[[0,1,0,1,0],[9,6]]
sign in to submit