Top K Frequent Elements LeetCode Problem 347 [Python Solution]

So you are interested in the fascinating LeetCode problem of finding the k most frequent elements in an array, the Top K Frequent Elements LeetCode problem.

This problem is not only intriguing but also offers multiple approaches for solving it efficiently.

We will explore the problem overview, the constraints, a brute-force approach, and finally, an efficient solution called “Bucket Sort.”

Problem Overview

Imagine you have an integer array, nums, and an integer, k.

Your task is to return the k most frequent elements from the array, and you can present the answer in any order.

To clarify, let’s take an example.

Given the array [1, 1, 1, 2, 2, 3] and k = 2, the expected output is [1, 2] because 1 occurs three times, and 2 occurs twice.

Example 1:

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

Example 2:

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

Problem Constraints

Now, let’s understand the constraints of this problem:

The length of the array, nums, is between 1 and 105.
The values in nums are between -104 and 104.
The value of k falls within the range [1, the number of unique elements in the array].
The answer is guaranteed to be unique.

With these constraints in mind, let’s explore different approaches to solve this problem.

Brute-force Approach

One straightforward way to solve this problem is by using a brute-force approach.

We can iterate through the array, count the occurrences of each element, and then select the k elements with the highest frequencies.

Here’s a Python code snippet for the brute-force approach:

def topKFrequent(nums, k):
    # Initialize a dictionary to store element counts
    count = {}

    # Count the occurrences of each element in nums
    for num in nums:
        count[num] = count.get(num, 0) + 1

    # Sort the elements by their counts in descending order
    sorted_elements = sorted(count.keys(), key=lambda x: -count[x])

    # Return the top k frequent elements
    return sorted_elements[:k]

While this approach works, it has a time complexity of O(n log n) due to the sorting step.

Solving Top K Frequent Elements Efficiently with Bucket Sort

Now, let’s explore a more efficient approach that achieves a time complexity of O(n).

This approach leverages a technique called “Bucket Sort.” Instead of sorting all elements, we create a special array where each index represents the frequency of elements, and the values are lists of elements with that frequency.

Here’s the Python code for this efficient approach:

View on GitHub ➹

def topKFrequent(self, nums: List[int], k: int) -> List[int]:
    # Initialize a dictionary to store element counts
    count = {}
    
    # Count the occurrences of each element in nums
    for num in nums:
        count[num] = count.get(num, 0) + 1
    
    # Create a frequency array with empty lists
    max_freq = max(count.values())
    frequency = [[] for _ in range(max_freq + 1)]
    
    # Fill the frequency array with elements
    for num, freq in count.items():
        frequency[freq].append(num)
    
    # Initialize the result array
    result = []
    
    # Iterate through the frequency array in descending order
    for i in range(max_freq, 0, -1):
        if k == 0:
            break
        if frequency[i]:
            result.extend(frequency[i])
            k -= len(frequency[i])
    
    return result

This approach takes advantage of the fact that the frequency array’s size is proportional to the input size, making it more efficient than sorting the entire array.

Reasoning Behind Our Efficient Approach

The efficient approach leverages the property that the frequency array’s size is bounded by the input size and the fact that we only need to find the top k frequent elements.

By organizing elements in the frequency array based on their frequencies, we can efficiently extract the k most frequent elements in linear time.

Conclusion

In this blog post, we tackled the problem of finding the k most frequent elements in an array.

We explored a brute-force approach and an efficient solution using Bucket Sort.

While the brute-force approach works, it has a time complexity of O(n log n), whereas the efficient approach achieves a time complexity of O(n).

Bucket Sort provides an elegant and efficient solution to this problem, making it a valuable technique to have in your algorithm toolbox.

Now that you’ve learned how to solve this problem, you can apply these concepts to similar challenges and enhance your algorithmic problem-solving skills.

Drop your newly learned Top K Frequent Elements solution on LeetCode today.

Feel free to comment, ask questions, make suggestions, and share this content with others to help them on their coding journey.

Happy coding!

Top K Frequent Elements LeetCode Problem 347 [Python Solution]

Top K Frequent Elements Question