We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Top K Frequent Elements

Number: 347

Difficulty: Medium

Paid? No

Companies: Meta, Amazon, Google, Microsoft, Apple, Bloomberg, Oracle, Uber, Goldman Sachs, ByteDance, Nutanix, Salesforce, Twilio, Microstrategy, TikTok, Avito, Intuit, Walmart Labs, Netflix, PayPal, Chewy, Pinterest, Adobe, Yahoo, Yandex, Tesla, Dropbox, Snap, Docusign, eBay, Nvidia, Visa, J.P. Morgan, Arista Networks, DoorDash, Yelp, Pocket Gems

Problem Description

Given a non-empty integer array and an integer k, return the k most frequent elements. The problem guarantees that there is a unique answer and that the order of the returned elements can be arbitrary.

Key Insights

  • Count the frequency of each element using a hash table.
  • Use bucket sort to achieve linear time complexity by grouping numbers by their frequency.
  • Traverse the frequency buckets from highest to lowest to collect the k most frequent elements.
  • Alternative approaches include using heaps or Quickselect, but bucket sort meets the follow-up requirement of better than O(n log n) time complexity.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the array (bucket sort and frequency counting are linear). Space Complexity: O(n) for storing the counts and buckets.

Solution

The solution starts by counting the frequency of each element with a hash table (or dictionary). Then, we create an array of buckets where the index represents the frequency. Each bucket holds the numbers that appear with that frequency. Finally, we iterate over the buckets in reverse order (from high frequency to low) and collect elements until we have k of them. This bucket sort approach avoids the higher complexity of sorting a list of frequencies and guarantees linear time performance.

Code Solutions

# Python solution using bucket sort

def topKFrequent(nums, k):
    # Count the frequency of each element in nums
    frequency = {}
    for num in nums:
        frequency[num] = frequency.get(num, 0) + 1

    # Create buckets where index represents frequency
    n = len(nums)
    buckets = [[] for _ in range(n + 1)]
    for num, count in frequency.items():
        buckets[count].append(num)

    # Gather the k most frequent elements
    result = []
    # Iterate over buckets in reverse order (highest frequency first)
    for freq in range(n, 0, -1):
        for num in buckets[freq]:
            result.append(num)
            if len(result) == k:
                return result

# Example usage:
# print(topKFrequent([1,1,1,2,2,3], 2)) -> Output: [1, 2]
← Back to All Questions