LeetCode 347: Top K Frequent Elements Solution

Master LeetCode problem 347 (Top K Frequent Elements), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

347. Top K Frequent Elements

Medium

Array Hash Table Divide and Conquer Sorting Heap (Priority Queue)Bucket Sort Counting Quickselect

Problem Explanation

Explanation

To solve this problem, we can use a hashmap to store the frequency of each element in the array. Then, we can use a priority queue (min-heap) to keep track of the top k frequent elements based on their frequencies. We iterate through the hashmap, adding elements to the priority queue until it reaches size k. If a new element has a higher frequency than the smallest element in the priority queue, we remove the smallest element and add the new element. Finally, we extract the top k elements from the priority queue and return them.

Time complexity: O(n + k log k) where n is the number of elements in the array
Space complexity: O(n) for the hashmap and priority queue

Solution Code

import java.util.*;

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        for (int num : nums) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }
        
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> frequencyMap.get(a) - frequencyMap.get(b));
        
        for (int num : frequencyMap.keySet()) {
            pq.offer(num);
            if (pq.size() > k) {
                pq.poll();
            }
        }
        
        int[] result = new int[k];
        for (int i = k - 1; i >= 0; i--) {
            result[i] = pq.poll();
        }
        
        return result;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 347 (Top K Frequent Elements)?

This page provides optimized solutions for LeetCode problem 347 (Top K Frequent Elements) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 347 (Top K Frequent Elements)?

The time complexity for LeetCode 347 (Top K Frequent Elements) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 347 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 347 in Java, C++, or Python.

Back to LeetCode Solutions