Definition

Top k is a category o problems that usually ask for the k most or least frequent elements, k biggest or smallest values in an array or in a stream.

Problems

Kth Largest Element in an Array

class Solution {
	public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> q = new PriorityQueue<Integer>();

        for(int e: nums) {
            q.add(e);
            if(q.size() > k) 
                q.remove();
        }

        return q.peek();
	}	
}

In this case, a priority Queue/Min heap is more efficient than just a sort because the queue won’t exceed k elements and having a time complexity of O(n log k) instead of O(n log n). Also, the space complexity will be k

Top k most frequent items in an array

Given an array, return the top 3 most frequent elements

public class Main {
    public static void main(String[] args) {
        String[] letters = new String[]{"@", "@", "@", "@", "#", "#", "#", "$", "$", "&"};

        var frequencies = new HashMap<String, Integer>();        

        for(var e: letters)
            frequencies.put(e, frequencies.getOrDefault(e, 0) + 1);

        System.out.println(frequencies.toString());
        // {"@"=4, "#"=3, "$"=2, "&"=1}

        var q = new PriorityQueue<String>((a, b) -> {
            return frequencies.get(a) - frequencies.get(b);
        });

        for(var e: frequencies.keySet()) {
            q.add(e);
            if(q.size() > 3)
                q.remove();
        }
            
        System.out.println(q.toString());
        // [$, @, #]
    }
}

Here a min heap is used with a different setup to sort the elements based on their frequency instead of their values.

The complexity here is linear to count the frequencies and O(n log k) to sort the most frequent;

K closest points to the origin

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        var result = new int[k][2];        
        var distances = new HashMap<Integer, Double>();

        // Calculate all the distances once
        for(int i=0; i < points.length; i++) {
            var currentPoint = points[i];
            
            double distance = Math.sqrt(
                currentPoint[0] * currentPoint[0] + 
                currentPoint[1] * currentPoint[1]
            );
            
            distances.put(i, distance);
        }

        var pq = new PriorityQueue<Integer>((a, b) -> {
            return distances.get(b).compareTo(distances.get(a));
        });

        // Select the smallest using a priorityQueue
        for(int i=0; i < points.length; i++) {
            pq.add(i);
            if(pq.size() > k) {
                pq.remove();
            }
        }
        
        // build the result
        for(int i=0; i < k; i++) {
            var item = pq.poll();
            if(item != null) {
                result[i][0] = points[item][0];
                result[i][1] = points[item][1];
            }
        }
        
        return result;
    }
}