🚀 Mastering the Top ‘K’ Elements Pattern – With Java Code

The Top ‘K’ Elements pattern is an essential technique in coding interviews. It helps solve problems where you need to identify the largest, smallest, or most frequent 'K' elements efficiently – often using heaps (priority queues).

---

💡 When to Use the Top ‘K’ Pattern

Use this pattern when:

• You’re asked for K largest/smallest/frequent items
• You need to track top K elements dynamically
• Sorting the entire dataset is inefficient or not allowed

---

🔧 Key Data Structure – Heap (PriorityQueue)

Java's PriorityQueue implements a min-heap by default. To simulate a max-heap, use a custom comparator or Collections.reverseOrder().

---

📦 Common Variants and Java Code Snippets

---

✅ 1. Find the K Largest Numbers in an Array

public List<Integer> findKLargest(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();

    for (int num : nums) {
        minHeap.offer(num);
        if (minHeap.size() > k) {
            minHeap.poll(); // remove the smallest
        }
    }

    return new ArrayList<>(minHeap); // contains k largest
}

🕒 Time: O(n log k)

📦 Space: O(k)

---

✅ 2. Find the K Smallest Numbers

public List<Integer> findKSmallest(int[] nums, int k) {
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

    for (int num : nums) {
        maxHeap.offer(num);
        if (maxHeap.size() > k) {
            maxHeap.poll(); // remove the largest
        }
    }

    return new ArrayList<>(maxHeap); // contains k smallest
}

---

✅ 3. Top K Frequent Elements

public List<Integer> topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> freqMap = new HashMap<>();
    for (int num : nums) {
        freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
    }

    PriorityQueue<Map.Entry<Integer, Integer>> minHeap =
        new PriorityQueue<>(Comparator.comparingInt(Map.Entry::getValue));

    for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
        minHeap.offer(entry);
        if (minHeap.size() > k) {
            minHeap.poll();
        }
    }

    List<Integer> result = new ArrayList<>();
    for (Map.Entry<Integer, Integer> entry : minHeap) {
        result.add(entry.getKey());
    }

    return result;
}

🧠 Common in social media & search engine interview problems.

---

✅ 4. K Closest Numbers to a Target

public List<Integer> findKClosest(int[] nums, int k, int x) {
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(
        (a, b) -> Math.abs(b - x) - Math.abs(a - x)
    );

    for (int num : nums) {
        maxHeap.offer(num);
        if (maxHeap.size() > k) {
            maxHeap.poll();
        }
    }

    return new ArrayList<>(maxHeap);
}

---

✅ 5. Kth Largest Element in an Array (LeetCode 215)

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

    for (int num : nums) {
        minHeap.offer(num);
        if (minHeap.size() > k) {
            minHeap.poll();
        }
    }

    return minHeap.peek();
}

---

✅ 6. Sort a K-Sorted Array (Nearly Sorted)

public int[] sortKSortedArray(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    int index = 0;

    for (int i = 0; i < nums.length; i++) {
        minHeap.offer(nums[i]);
        if (minHeap.size() > k) {
            nums[index++] = minHeap.poll();
        }
    }

    while (!minHeap.isEmpty()) {
        nums[index++] = minHeap.poll();
    }

    return nums;
}

---

✅ 7. Kth Smallest Element in a Matrix

Use min-heap and matrix cell tracking.

class Cell {
    int value, row, col;
    Cell(int value, int row, int col) {
        this.value = value; this.row = row; this.col = col;
    }
}

public int kthSmallest(int[][] matrix, int k) {
    PriorityQueue<Cell> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a.value));
    int n = matrix.length;

    for (int i = 0; i < Math.min(n, k); i++) {
        minHeap.offer(new Cell(matrix[i][0], i, 0));
    }

    int count = 0;
    while (!minHeap.isEmpty()) {
        Cell curr = minHeap.poll();
        count++;
        if (count == k) return curr.value;

        if (curr.col + 1 < n) {
            minHeap.offer(new Cell(matrix[curr.row][curr.col + 1], curr.row, curr.col + 1));
        }
    }

    return -1;
}

---

📚 LeetCode Problems to Practice

Problem	Link
Top K Frequent Elements	LeetCode 347
Kth Largest Element	LeetCode 215
K Closest Points to Origin	LeetCode 973
Sort a K Sorted Array	GFG Problem
Kth Smallest Element in a Matrix	LeetCode 378

---

📈 Time & Space Complexities Overview

Problem	Time Complexity	Space Complexity
K largest/smallest	O(n log k)	O(k)
Top K frequent	O(n log k)	O(n)
Kth largest/smallest	O(n log k)	O(k)
K sorted array	O(n log k)	O(k)

---

💬 Interviewer May Ask

• Why heap over full sort?
• How to implement max-heap in Java?
• Can you solve without a heap? (e.g., Quickselect for Kth largest)
• What's the difference between a heap and a priority queue?

---

🧠 Bonus – Custom MaxHeap in Java

PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);

---

✅ Summary

Use Case	Heap Type
K Largest/Smallest Numbers	Min/Max Heap
Top K Frequent	Min Heap
K Closest Numbers	Max Heap
Kth Largest	Min Heap
Sort K-Sorted Array	Min Heap

---

🎁 Final Tip

🧩 Don’t memorize code — understand the heap size logic and comparisons.

📌 Practice makes this pattern second nature. You'll often see a combination of heap + hashmap + comparator — nail these and you’re ready for real interviews.

---