#347

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Top K Frequent Elements

Find the k most frequent elements from an array using efficient algorithms like hashing and sorting.

array hash table divide and conquer sorting heap priority queue

Problem Statement

Given an integer array nums and an integer k, return the k most frequent elements in the array. You may return the answer in any order, but it must correctly represent the most frequent values in the input list.

For example, if the input is nums = [1,1,1,2,2,3] and k = 2, the result should be [1, 2], since 1 appears most frequently, followed by 2. The solution should scale well for large arrays and ensure correctness across different test cases.

Examples

Example 1

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

Output: [1,2]

Example details omitted.

Example 2

Input: nums = [1], k = 1

Output: [1]

Example details omitted.

Constraints

1 <= nums.length <= 105
-104 <= nums[i] <= 104
k is in the range [1, the number of unique elements in the array].
It is guaranteed that the answer is unique.

Solution Approach

Using a Hash Map and Sorting

First, count the frequency of each element using a hash map. Then, sort the elements based on their frequency and return the top k frequent elements. This is a straightforward approach that leverages the efficiency of sorting.

Heap (Priority Queue) for Optimization

To optimize the sorting step, we can use a min-heap (priority queue) to keep track of the top k frequent elements. This reduces the complexity of sorting and improves performance, especially for large datasets.

Bucket Sort for Constant Time Lookup

Using bucket sort is another viable method. In this approach, elements are grouped by their frequency, and the k most frequent elements can be selected from the highest frequency buckets. This method is efficient when the range of frequencies is limited.

Complexity Analysis

Metric	Value
Time	\mathcal{O}(N)
Space	up to

The time complexity for the hash map and sorting approach is O(N log N) due to the sorting step. The heap-based solution optimizes this to O(N log k). The bucket sort method can achieve O(N) time complexity in some cases, but it depends on the frequency distribution.

What Interviewers Usually Probe

Evaluates the candidate’s understanding of hash maps and sorting algorithms.
Assesses how well the candidate can optimize solutions using data structures like heaps.
Checks the candidate's ability to apply trade-offs for time and space complexity in algorithm design.

Common Pitfalls or Variants

Common pitfalls

Failing to consider the optimization of sorting by using a heap.
Incorrectly handling cases where multiple elements have the same frequency.
Overlooking edge cases where the array length is small or all elements have the same frequency.

Follow-up variants

Return the k least frequent elements instead of the most frequent ones.
Modify the problem to allow a dynamic stream of elements instead of a static array.
Return the top k elements but with custom ordering based on an additional condition.

FAQ

How can I optimize my solution for large arrays in the Top K Frequent Elements problem?

Using a heap to store the top k frequent elements minimizes sorting overhead, improving performance for large datasets.

Is sorting necessary in the Top K Frequent Elements problem?

No, sorting can be replaced with a heap or bucket sort for improved time complexity in some cases.

What are the time complexities of different approaches for solving the Top K Frequent Elements problem?

Sorting the elements leads to O(N log N) complexity, while using a heap optimizes this to O(N log k). Bucket sort can achieve O(N) in some scenarios.

What data structures are commonly used in solving the Top K Frequent Elements problem?

Hash maps are used for counting frequencies, while heaps and bucket sort are used for efficiently selecting the top k elements.

How does GhostInterview help in solving the Top K Frequent Elements problem?

GhostInterview offers optimized solutions, practical tips on choosing the best approach, and real-time performance feedback to ensure efficient solutions for Top K Frequent Elements.

terminal

Solution

Solution 1: Hash Table + Priority Queue (Min Heap)

We can use a hash table $\textit{cnt}$ to count the occurrence of each element, and then use a min heap (priority queue) to store the top $k$ frequent elements.

1

2

3

4

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        cnt = Counter(nums)
        return [x for x, _ in cnt.most_common(k)]

Continue Practicing

#692 top k frequent words #451 sort characters by frequency #169 majority element