5. Top K frequent elements

The Top K Frequent Elements problem on LeetCode is a classic problem that asks you to return the k most frequent elements in a given array of integers. Let’s go through solutions from brute force to optimal, focusing on different approaches with increasing efficiency.

---

Problem Statement

Input: An integer array nums and an integer k.
Output: Return the k most frequent elements in the array.

Example:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1, 2]

---

Approach 1: Brute Force (O(n²))

Idea:
Count the frequency of each number by comparing each element with others in the array, and then pick the top k elements.

Code (Brute Force)

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class TopKFrequentBruteForce {
    public static List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> result = new ArrayList<>();
        List<Integer> visited = new ArrayList<>();

        for (int i = 0; i < nums.length; i++) {
            if (visited.contains(nums[i])) continue;  // Skip already processed numbers
            int count = 0;
            for (int j = 0; j < nums.length; j++) {
                if (nums[i] == nums[j]) count++;
            }
            visited.add(nums[i]);
            result.add(nums[i] + ":" + count);  // Just for debugging frequency
        }

        // Sort the result by frequency (using custom comparison logic)
        result.sort((a, b) -> Integer.compare(Integer.valueOf(b.split(":")[1]), Integer.valueOf(a.split(":")[1])));

        List<Integer> topK = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            topK.add(Integer.valueOf(result.get(i).split(":")[0]));
        }
        return topK;
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 2, 2, 3};
        int k = 2;
        System.out.println(topKFrequent(nums, k));  // Output: [1, 2]
    }
}

Time Complexity: O(n²)

• We are using a nested loop to count frequencies, leading to quadratic time complexity.
• This is inefficient for large inputs.

---

Approach 2: HashMap + Sorting (O(n log n))

Idea:

1. Use a HashMap to count the frequency of each element in nums.
2. Sort the map by frequency and return the top k elements.

Code (HashMap + Sorting)

import java.util.*;

public class TopKFrequentSorting {
    public static List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freqMap = new HashMap<>();

        // Step 1: Count the frequency of each element
        for (int num : nums) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }

        // Step 2: Sort map entries by frequency in descending order
        List<Integer> result = new ArrayList<>(freqMap.keySet());
        result.sort((a, b) -> freqMap.get(b) - freqMap.get(a));

        // Step 3: Return the top k elements
        return result.subList(0, k);
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 2, 2, 3};
        int k = 2;
        System.out.println(topKFrequent(nums, k));  // Output: [1, 2]
    }
}

Time Complexity: O(n log n)

• Counting the frequencies takes O(n) time.
• Sorting the frequencies takes O(n log n) time.

---

Approach 3: HashMap + Min-Heap (O(n log k))

Idea:

1. Use a HashMap to store the frequency of each element.
2. Use a Min-Heap (Priority Queue) to store the top k elements based on their frequency.
3. Return the top k frequent elements by extracting from the heap.

Code (HashMap + Min-Heap)

import java.util.*;

public class TopKFrequentMinHeap {
    public static List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freqMap = new HashMap<>();

        // Step 1: Count the frequency of each element
        for (int num : nums) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }

        // Step 2: Use a Min-Heap to store the top k elements
        PriorityQueue<Integer> minHeap = new PriorityQueue<>((a, b) -> freqMap.get(a) - freqMap.get(b));

        for (int num : freqMap.keySet()) {
            minHeap.add(num);
            if (minHeap.size() > k) {
                minHeap.poll();  // Remove the least frequent element
            }
        }

        // Step 3: Extract elements from the heap
        List<Integer> result = new ArrayList<>();
        while (!minHeap.isEmpty()) {
            result.add(minHeap.poll());
        }
        Collections.reverse(result);  // To get the elements in descending order
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 2, 2, 3};
        int k = 2;
        System.out.println(topKFrequent(nums, k));  // Output: [1, 2]
    }
}

Time Complexity: O(n log k)

• Counting the frequencies takes O(n) time.
• Each insertion and deletion in the heap takes O(log k) time, making it optimal for large n and small k.

---

Approach 4: HashMap + Bucket Sort (O(n))

Idea:
Since the maximum frequency of any element can’t exceed n, we can use bucket sort to sort elements by frequency in linear time.

Code (HashMap + Bucket Sort)

import java.util.*;

public class TopKFrequentBucketSort {
    public static List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freqMap = new HashMap<>();

        // Step 1: Count the frequency of each element
        for (int num : nums) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }

        // Step 2: Create buckets (index = frequency)
        List<Integer>[] buckets = new List[nums.length + 1];
        for (int key : freqMap.keySet()) {
            int frequency = freqMap.get(key);
            if (buckets[frequency] == null) {
                buckets[frequency] = new ArrayList<>();
            }
            buckets[frequency].add(key);
        }

        // Step 3: Collect top k frequent elements from buckets
        List<Integer> result = new ArrayList<>();
        for (int i = buckets.length - 1; i >= 0 && result.size() < k; i--) {
            if (buckets[i] != null) {
                result.addAll(buckets[i]);
            }
        }
        return result.subList(0, k);
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 2, 2, 3};
        int k = 2;
        System.out.println(topKFrequent(nums, k));  // Output: [1, 2]
    }
}

Time Complexity: O(n)

• Counting frequencies takes O(n).
• Bucket sort with fixed-size buckets takes O(n).

---