Leetcode 347 - Top K Frequent Elements

Difficulty: medium

Table of contents

Open Table of contents

Problem

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

Example 1:

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

Example 2:

Input: nums = [1], k = 1
Output: [1]

Constraints:

Follow up: Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.

Explanation/Approach

This problem requires us to identify the k most frequent elements in an array. A combination of a hash table and a heap can efficiently solve this problem.

Hash Table and Heap Approach:

Hash Table and Bucket Sort Approach:

This problem can be efficiently solved by using a hash table for frequency count and a list of lists (bucket sort) to organize elements by their frequencies.

Solution: Hash Table and Heap

import heapq

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # Frequency count of each element
        frequency = {}
        for num in nums:
            frequency[num] = frequency.get(num, 0) + 1

        # Min-heap to store the top k frequent elements
        min_heap = []
        for num, freq in frequency.items():
            heapq.heappush(min_heap, (freq, num))
            # If the heap size exceeds k, remove the smallest frequency element
            if len(min_heap) > k:
                heapq.heappop(min_heap)

        # Extract the elements from the heap
        top_k_elements = [num for freq, num in min_heap]
        return top_k_elements

Time and Memory Complexity

The time complexity of this solution is O(n + k log n), where n is the number of elements in nums. Building the frequency hash table takes O(n), and each heap operation takes O(log n). The space complexity is O(n) to store the frequency of each element.

Explanation

This solution first counts the frequency of each element using a hash table. Then, it uses a min-heap to maintain the top k frequent elements. By popping elements from the heap when its size exceeds k, we ensure that only the most frequent elements remain. Finally, the elements in the heap are the required k most frequent elements.

Visual Representation

Consider the input nums = [1,1,1,2,2,3] and k = 2.

  1. Frequency Count:

    • The frequency count process will create a hash table representing the frequency of each unique number in nums.
    • Frequency Table: {1: 3, 2: 2, 3: 1}.

  2. Building the Heap:

    • We start building the min-heap using the frequency count.
    • Initially, the heap is empty. We add elements as (frequency, number) pairs.
    • After adding (3, 1), the heap is [(3, 1)].
    • Adding (2, 2), the heap becomes [(2, 2), (3, 1)].
    • When (1, 3) is added, the heap would become [(1, 3), (3, 1), (2, 2)]. Since the heap size now exceeds k, we pop the smallest element (1, 3). The heap is back to [(2, 2), (3, 1)].

  3. Result:

    • The final heap contains the k most frequent elements, which are [(2, 2), (3, 1)].
    • The top k elements extracted from the heap are [2, 1].
[1,1,1,2,2,3]  --->  Frequency Table: {1: 3, 2: 2, 3: 1}
                         |
                         V
                      Min Heap
                     -----------
  Add (3, 1)       |     (3, 1)    |
  Add (2, 2)       | (2, 2), (3, 1)|
  Add (1, 3)       | (1, 3), (2, 2), (3, 1) |
                     -----------
                         |
                         V
  Pop (1, 3)       | (2, 2), (3, 1) |
                     -----------
                         |
                         V
        Top K Elements: [2, 1]

Solution: Hash Table and Bucket Sort

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # Frequency count of each element
        frequency = {}
        for num in nums:
            frequency[num] = frequency.get(num, 0) + 1

        # Initialize buckets for each possible frequency
        buckets = [[] for _ in range(len(nums) + 1)]
        for num, freq in frequency.items():
            buckets[freq].append(num)

        # Extract the top k frequent elements
        top_k_elements = []
        for i in range(len(buckets) - 1, 0, -1):
            for num in buckets[i]:
                top_k_elements.append(num)
                if len(top_k_elements) == k:
                    return top_k_elements

Time and Memory Complexity

The time complexity of this solution is O(n), where n is the number of elements in nums, since each element is processed once to build the frequency table and then once more when building the buckets. The space complexity is also O(n) for storing the frequency table and the buckets.

Explanation

This approach uses a hash table to count the frequency of each element. Then, it uses a list of lists, where each list represents a bucket corresponding to a specific frequency. The elements are placed into these buckets based on their frequency. Finally, the buckets are iterated in reverse order to collect the k most frequent elements.

Visual Representation

Consider the input nums = [1,1,1,2,2,3] and k = 2.

  1. Frequency Count:

    • The frequency count process will create a hash table: {1: 3, 2: 2, 3: 1}.

  2. Buckets Formation:

    • Create buckets for each possible frequency. For our example, since the maximum frequency is 3, we create 4 buckets (including one for frequency 0, which remains empty).
    • Bucket 1: [3]
    • Bucket 2: [2]
    • Bucket 3: [1]

  3. Extracting Top K Elements:

    • Start from the highest frequency bucket and move downwards.
    • From Bucket 3, pick [1].
    • From Bucket 2, pick [2].
    • We have our top k elements [1, 2].
[1,1,1,2,2,3]  --->  Frequency Table: {1: 3, 2: 2, 3: 1}
                         |
                         V
                    Buckets Formation
                     -------------------
  Bucket 3: [1]   |

   Bucket 2: [2]    |   Bucket 1: [3]
                     -------------------
                         |
                         V
        Top K Elements: [1, 2]