Top K Elements

// Maintain a min-heap of size k — the root is the kth largest
public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // min at top
    for (int num : nums) {
        minHeap.offer(num);
        if (minHeap.size() > k) minHeap.poll(); // remove smallest
    }
    return minHeap.peek(); // kth largest is the smallest in heap of size k
}
// Time: O(n log k), Space: O(k)

public int findKthLargest(int[] nums, int k) {
    return quickSelect(nums, 0, nums.length - 1, nums.length - k);
}
int quickSelect(int[] nums, int lo, int hi, int targetIdx) {
    int pivot = nums[hi];
    int p = lo;
    for (int i = lo; i < hi; i++)
        if (nums[i] <= pivot) swap(nums, i, p++);
    swap(nums, p, hi);

    if (p == targetIdx) return nums[p];
    return p < targetIdx
        ? quickSelect(nums, p+1, hi, targetIdx)
        : quickSelect(nums, lo, p-1, targetIdx);
}
void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }
// Time: O(n) average, O(n²) worst

public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int n : nums) freq.merge(n, 1, Integer::sum);

    // Min-heap by frequency
    PriorityQueue<int[]> heap = new PriorityQueue<>((a,b) -> a[1] - b[1]);
    for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
        heap.offer(new int[]{e.getKey(), e.getValue()});
        if (heap.size() > k) heap.poll();
    }

    int[] result = new int[k];
    for (int i = k-1; i >= 0; i--) result[i] = heap.poll()[0];
    return result;
    // Time: O(n log k)
}

public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int n : nums) freq.merge(n, 1, Integer::sum);

    // Bucket: index = frequency
    List<Integer>[] bucket = new List[nums.length + 1];
    for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
        int f = e.getValue();
        if (bucket[f] == null) bucket[f] = new ArrayList<>();
        bucket[f].add(e.getKey());
    }

    List<Integer> result = new ArrayList<>();
    for (int f = bucket.length - 1; f >= 0 && result.size() < k; f--)
        if (bucket[f] != null) result.addAll(bucket[f]);

    return result.stream().mapToInt(Integer::intValue).toArray();
}

public int[][] kClosest(int[][] points, int k) {
    // Max-heap by distance — keep the k smallest
    PriorityQueue<int[]> maxHeap = new PriorityQueue<>(
        (a, b) -> (b[0]*b[0]+b[1]*b[1]) - (a[0]*a[0]+a[1]*a[1]));
    for (int[] p : points) {
        maxHeap.offer(p);
        if (maxHeap.size() > k) maxHeap.poll(); // remove furthest
    }
    return maxHeap.toArray(new int[0][]);
}

public String frequencySort(String s) {
    Map<Character, Integer> freq = new HashMap<>();
    for (char c : s.toCharArray()) freq.merge(c, 1, Integer::sum);

    PriorityQueue<Map.Entry<Character, Integer>> maxHeap =
        new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());
    maxHeap.addAll(freq.entrySet());

    StringBuilder sb = new StringBuilder();
    while (!maxHeap.isEmpty()) {
        Map.Entry<Character, Integer> e = maxHeap.poll();
        sb.append(String.valueOf(e.getKey()).repeat(e.getValue()));
    }
    return sb.toString();
}