TopK

TopK Strings with longest length

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.

• 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

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.

• Use a minHeap to store sum

• Pull out the sum and put new sum based on previous nums1 + 1

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)

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)

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)

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)

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);
    }
}