Top K Frequent Elements

Imagine you’re analyzing data from a music streaming service. You want to find the top 3 most played songs from a playlist. That’s exactly what this problem helps us solve - finding the k most frequent elements in a list!

Problem Statement

Given an array of numbers and an integer k, return the k most frequent elements. You can return the answer in any order.

Solution Approaches

Let’s explore different ways to solve this problem using various programming languages:

from collections import Counter
import heapq

def topKFrequent(nums, k):
    # Count frequencies
    count = Counter(nums)

    # Keep k most frequent elements using min-heap
    heap = []
    for num, freq in count.items():
        heapq.heappush(heap, (freq, num))
        if len(heap) > k:
            heapq.heappop(heap)

    # Extract results
    return [num for freq, num in heap]

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> count;
        for (int num : nums) {
            count[num]++;
        }

        priority_queue<pair<int, int>> pq;
        for (auto& pair : count) {
            pq.push({pair.second, pair.first});
        }

        vector<int> result;
        while (k--) {
            result.push_back(pq.top().second);
            pq.pop();
        }
        return result;
    }
};

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

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

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[1] - a[1]);
        for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
            pq.offer(new int[] {
                    entry.getKey(), entry.getValue()
            });
        }

        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = pq.poll()[0];
        }
        return result;
    }
}

Step-by-Step Explanation

Let’s walk through the solution using a concrete example:

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

1. First, we count the frequencies of each number:

   count = {1: 3, 2: 2, 3: 1}
   

2. Process each number-frequency pair through the heap:

   • Add (3,1): heap = [(3,1)]
   • Add (2,2): heap = [(2,2), (3,1)]
   • Add (1,3): heap = [(2,2), (3,1)] # (1,3) gets removed as it’s smallest

3. Final result: [1,2] - these are the two most frequent elements

Time and Space Complexity

Let’s analyze the efficiency of our solution:

• Time Complexity: O(n log k)

  • Counting frequencies: O(n)
  • Heap operations: O(log k) for each unique number
  • Where n is the length of input array

• Space Complexity: O(n)

  • HashMap to store frequencies: O(n)
  • Heap to store k elements: O(k)
  • Since k ≤ n, overall space is O(n)

Real-World Applications

This algorithm pattern is incredibly useful in various real-world scenarios:

1. Content Recommendations

   • Finding most-watched videos
   • Identifying trending hashtags
   • Suggesting popular products

2. System Monitoring

   • Tracking frequent error codes
   • Identifying high-traffic IP addresses
   • Monitoring resource usage patterns

3. Data Analysis

   • Finding most common customer behaviors
   • Analyzing peak usage periods
   • Identifying popular search terms

Key Takeaways

1. Hash maps are perfect for counting frequencies efficiently
2. Heaps help us maintain top k elements with optimal performance
3. This pattern can be applied to find top k of anything - words, users, events
4. Consider using Counter in Python for simplified frequency counting
5. Priority queues in different languages offer similar functionality with different syntax

Practice Problems

To master this concept, try these related problems:

Remember: The key to mastering these problems is understanding when to use hash maps for counting and heaps for maintaining top k elements efficiently.