TIC
The Interns Company

Top K Frequent Elements

MediumAcceptance: 64.8%
ArrayHash TableDivide and ConquerSortingHeap (Priority Queue)Bucket SortCountingQuickselect

Problem Statement

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Constraints:

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4
  • k is in the range [1, the number of unique elements in the array]
  • It is guaranteed that the answer is unique.

Input Format:

  • An integer array nums
  • An integer k

Output Format:

  • Return the k most frequent elements in any order.

Examples:

Example 1:

Input:

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

Output:

[1,2]

Explanation:

The elements 1 and 2 appear the most frequently. 1 appears 3 times and 2 appears 2 times.

Example 2:

Input:

nums = [1], k = 1

Output:

[1]

Explanation:

The element 1 appears once, which is the only element in the array.

Solutions

Hash Map and Heap Approach

Time: O(n log k)
Space: O(n)

Count the frequency of each element using a hash map. Then use a min-heap of size k to keep track of the k most frequent elements.

Bucket Sort Approach

Time: O(n)
Space: O(n)

Count the frequency of each element using a hash map. Then use bucket sort where the bucket index represents the frequency. Iterate through the buckets from highest to lowest frequency to find the top k elements.

Algorithm Walkthrough

Example input: nums = [1,1,1,2,2,3]

Step-by-step execution:

  1. Count frequencies: {1: 3, 2: 2, 3: 1}
  2. Create bucket sort array with indices as frequencies: [[], [3], [2], [1], [], []]
  3. Start from highest frequency (bucket[3]): Add 1 to result. result = [1]
  4. Move to next highest (bucket[2]): Add 2 to result. result = [1, 2]
  5. We've found k=2 elements, so return [1, 2]

Hints

Hint 1
Count the frequency of each element using a hash map.
Hint 2
Sort the elements by frequency, or use a heap to efficiently find the k most frequent elements.
Hint 3
A more efficient approach is to use bucket sort or the quickselect algorithm.
Hint 4
For bucket sort, create buckets for each frequency and place elements in the appropriate bucket.

Video Tutorial

Top K Frequent Elements - Bucket Sort & Heap Approaches

YouTube•Learn the Top K Frequent Elements solution step-by-step

Video tutorials can be a great way to understand algorithms visually

Visualization

Visualize the frequency of each element in the array, and how the top k elements are selected.

Key visualization elements:

  • frequency counting
  • selection process

Asked By

AmazonGoogleMicrosoftFacebookAppleBloombergUber

Implementation Notes

This problem tests knowledge of frequency counting, sorting, and data structures like heaps. It's a common interview question that can be solved with multiple approaches, each with different trade-offs.