Top K Pins with Insert and Query
Problem statement
A pin board holds pins. Each pin has a unique integer ID and an integer score. Process the operations operations[0], operations[1], ... in order. values[i] holds the two numbers used by operations[i]:
"insert":values[i] = [pinId, score]. Add a pin with this ID and score. Pins are never removed, and their scores never change."top":values[i] = [k, 0]. Record the IDs of thekbest pins currently on the board, best first. A pin ranks higher when its score is higher. When two pins have the same score, the pin with the smaller ID ranks higher. If the board holds fewer thankpins, record all of them in rank order (an empty list if there are none).
A "top" operation only reads the board; it does not remove any pin. The value of k can be different for every query.
Return the recorded lists in order, one list per "top" operation. If there is no "top" operation, return an empty array.
Function
topKPins(operations: String[], values: int[][]) → int[][]Examples
Example 1
operations = ["insert","insert","insert","top","insert","top","top"]values = [[1,50],[2,80],[3,50],[2,0],[4,90],[3,0],[1,0]]return = [[2,1],[4,2,1],[4]]- After three inserts the pins rank as
2(score 80), then1and3(both score 50). Pin1comes before pin3because the scores tie and1is the smaller ID. top 2records[2,1].- Pin
4with score 90 is now the highest, sotop 3records[4,2,1]. - A query does not remove pins, so
top 1still finds pin4and records[4].
Example 2
operations = ["top","insert","insert","top"]values = [[3,0],[7,-5],[5,-5],[5,0]]return = [[],[5,7]]- The first
top 3runs before any insert, so it records an empty list. - Pins
7and5both have score -5. Pin5was inserted later but has the smaller ID, so it comes first. top 5asks for more pins than exist, so it records all of them:[5,7].
Example 3
operations = ["insert","insert","insert","insert"]values = [[10,3],[20,9],[30,1],[40,7]]return = []There is no top operation, so nothing is recorded and the answer is an empty array.
Constraints
1 <= operations.length <= 3000values.length == operations.lengthvalues[i].length == 2- Each
operations[i]is"insert"or"top". -10^9 <= values[i][j] <= 10^9- For an insert,
values[i] = [pinId, score]with0 <= pinId <= 10^6. - All inserted pin IDs are distinct.
- For a top,
values[i] = [k, 0]with1 <= k <= 1000. - The sum of
kover all top operations is at most1000.