# TopK

## TopK Strings with longest length

```java
public static List<String> topK(int k, Iterator<String> iter) {
    PriorityQueue<String> miniHeap = new PriorityQueue<>(k, new Comparator<String>(){
        @Override
        public int compare(String s1, String s2){
            return Integer.compare(s1.length(), s2.length());
        }
    });
    while(iter.hasNext()){
        String s = iter.next();
        if (s.length() > miniHeap.peek().length()) {
            miniHeap.add(s);
        }
    }
    return new ArrayList<>(miniHeap);
}
```

## 378 Kth Smallest Number in a Sorted Matrix

Find the kth smallest number in at row and column sorted matrix.

![](https://2249014260-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LrHBOmnlXe2UPlScnAC%2F-LrHBQ9YsXQZtBYE5uIM%2F-LrHBSx_F_7mgNEKGUkx%2Ftop_k.jpg?generation=1571189550004562\&alt=media)

* Pair class to store x and y index
* Put numbers in first column or first row
* Poll number and add new number based on previous row, loop k-1 times

```java
class pair{
    private int x, y, val;
    public pair(int x, int y, int val){
        this.x = x;
        this.y = y;
        this.val = val;
    }
}

public int kthSmallest(int[][] matrix, int k) {
    int m = matrix.length;
    int n = matrix[0].length;
    PriorityQueue<pair> minHeap = new PriorityQueue<>(m, (a, b) -> a.val - b.val);

    // add numbers in first column
    for(int i=0; i<m ;i++){
        minHeap.add(new pair(i, 0, matrix[i][0]));
    }
    for(int i=0; i<k-1; i++){
        pair min = minHeap.poll();
        if(min.y == n-1) continue;
        minHeap.add(new pair(min.x, min.y+1, matrix[min.x][min.y+1]));
    }
    return minHeap.peek().val;
}
```

## 373 Find K Pairs with Smallest Sums

You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k.

Define a pair (u,v) which consists of one element from the first array and one element from the second array.

Find the k pairs (u1,v1),(u2,v2) ...(uk,vk) with the smallest sums.

![](https://2249014260-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LrHBOmnlXe2UPlScnAC%2F-LrHBQ9YsXQZtBYE5uIM%2F-LrHBSxblH3Q5xmVYEmO%2Fk_pair.png?generation=1571189555732839\&alt=media)

* Use a minHeap to store sum
* Pull out the sum and put new sum based on previous nums1 + 1

```python
def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
    if not nums1 or not nums2: return []
    m, n = len(nums1), len(nums2)
    q = [(nums1[i]+nums2[0], i, 0) for i in range(m)]
    heapify(q)
    ans = []
    
    for i in range(m*n):
        s, p1, p2 = heappop(q)
        ans.append([nums1[p1], nums2[p2]])
        if len(ans) == k: break
            
        if p2 == n-1: continue
        heappush(q, (nums1[p1] + nums2[p2+1], p1, p2+1))
        
    return ans
```

## 692 Top K frequent word

Order the words by the frequency of them in the return list, the most frequent one comes first. If two words has the same frequency, the one with lower alphabetical order come first.

1. PriorityQueue: put the String in reverse compareTo order if they have same frequency
2. Time O(nlogk)

```java
public String[] topKFrequentWords(String[] words, int k) {
    if (k == 0 || words == null || words.length == 0){
        return new String[0];
    }

    Map<String, Integer> map = new HashMap<>();
    for (String word : words){
        map.put(word, map.getOrDefault(word, 0) + 1);
    }

    Comparator<String> cmp = new Comparator<String>(){
      public int compare(String s1, String s2){
        if (map.get(s1) == map.get(s2)){
            return s2.compareTo(s1);
            // alphabetical order in reverse order in minHeap 
        }else{
            return map.get(s1) - map.get(s2);
        }
      }  
    };

    Queue<String> minHeap = new PriorityQueue<>(k, cmp);

    for (String word: map.keySet()){
        minHeap.add(word);
        if (minHeap.size() > k) minHeap.poll();
    }

    String[] ans = new String[k];

    for (int i=k-1; i >=0; i--){
        ans[i] = minHeap.poll();
    }
    Arrays.sort(ans);
    return ans;
}
```

1. Bucket with list List\[] bucket, bucket\[i] is the frequency of string
2. Time avg O(nlogk), best O(klogk), worst O(nlogn)

```java
public List<String> topKFrequent(String[] words, int k) {
    Map<String, Integer> map = new HashMap<String, Integer>();
    for (String word:words) {
        map.put(word, map.getOrDefault(word, 0) + 1);
    }

    int N = words.length + 1;
    List<String>[] bucket = new List[N];
    for (String key: map.keySet()){
        int freq = map.get(key);
        if (bucket[freq] == null)
            bucket[freq] = new ArrayList<String>();
        bucket[freq].add(key);
    }

    List<String> ret = new ArrayList<String>();

    for (int i = N - 1; i >= 0 && ret.size() < k; i--) {
        if (bucket[i] != null) {
            Collections.sort(bucket[i]);
            ret.addAll(bucket[i]);
        }
    }
    return ((ArrayList)ret).subList(0, k);
}
```

1. Bucket with Trie \[code]\(<https://leetcode.com/problems/top-k-frequent-words/discuss/108399/Java-O(n)-solution-using-HashMap-BucketSort-and-Trie-22ms-Beat-81>)
2. Trie\[] bucket, bucket\[i] store the strings in same frequency
3. Time: O(n \* avgLenOfWord)

## 1244. TopK Leaderboard

Design a Leaderboard class, which has 3 functions:

1. `addScore(playerId, score)`: Update the leaderboard by adding `score` to the given player's score. If there is no player with such id in the leaderboard, add him to the leaderboard with the given `score`.
2. `top(K)`: Return the score sum of the top `K` players.
3. `reset(playerId)`: Reset the score of the player with the given id to 0 (in other words erase it from the leaderboard). It is guaranteed that the player was added to the leaderboard before calling this function.

O(nlogk)

```java
class Leaderboard {
    Map<Integer, Integer> map;
    public Leaderboard() {
        map = new HashMap<>();
    }
    
    public void addScore(int playerId, int score) {
        map.put(playerId, map.getOrDefault(playerId, 0) + score);
    }
    
    public int top(int K) {
        Queue<Integer> pq = new PriorityQueue<>();
        for (int v: map.values()){
            pq.add(v);
            if (pq.size() > K){
                pq.poll();
            }
        }
        int sum = 0;
        while (!pq.isEmpty()){
            sum += pq.poll();
        }
        return sum;
    }
    
    public void reset(int playerId) {
        map.put(playerId, 0);
    }
}
```

O(KlogN)

```java
class Leaderboard {
    Map<Integer, Integer> map;
    TreeMap<Integer, Integer> sorted;
    public Leaderboard() {
        map = new HashMap<>();
        sorted = new TreeMap<>(Collections.reverseOrder());
    }
    
    // O(logN) remove on TreeMap
    public void addScore(int playerId, int score) {
       if (!map.containsKey(playerId)) {
            map.put(playerId, score);
            sorted.put(score, sorted.getOrDefault(score, 0) + 1);
        } else {
            int preScore = map.get(playerId);
            sorted.put(preScore, sorted.get(preScore) - 1);
            if (sorted.get(preScore) == 0) {
                sorted.remove(preScore);
            }
            int newScore = preScore + score;
            map.put(playerId, newScore);
            sorted.put(newScore, sorted.getOrDefault(newScore, 0) + 1);
        }
    }
    
    // O(KlogN) K times * get on TreeMap (logN)
    public int top(int K) {
        int sum = 0;
        for (int key: sorted.keySet()){
            int times = sorted.get(key);
            for (int i=0; i < times; i++){
                sum += key;
                K-=1;
                if (K == 0) break;
            }
            if (K == 0) break;
        }
        return sum;
    }
    
    // O(logN) remove on TreeMap    
    public void reset(int playerId) {
       int preScore = map.get(playerId);
        sorted.put(preScore, sorted.get(preScore) - 1);
        if (sorted.get(preScore) == 0) {
            sorted.remove(preScore);
        }
        map.remove(playerId);
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://netjimmy.gitbook.io/code-interview-note/heap/topk.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.