347. Top K Frequent Elements

INFO

Problem: Top K Frequent Elements

Pattern: Frequency map / bucket sort

Top K Frequent Elements asks for the k values that appear most often. Sorting all values by frequency works, but bucket grouping can solve the problem in linear time.

The maximum possible frequency of any value is nums.count, so we can create buckets where the index represents a frequency. For example, bucket[3] stores numbers that appear three times.

Approach

1. Count how often each number appears.
2. Create an array of buckets from 0 through nums.count.
3. Place each number into the bucket matching its frequency.
4. Walk the buckets from highest frequency to lowest.
5. Append numbers until k elements have been collected.

This avoids sorting every unique number. We only scan the frequency buckets from high to low.

Swift Notes

The implementation uses [Int: Int] for counts and [[Int]] for buckets. The bucket array is initialized with empty arrays, then each key from the count dictionary is appended to the bucket for its frequency.

When reading from high frequency to low frequency, stride(from:to:by:) provides a clean reverse loop.

Complexity

• Time complexity: O(n).
• Space complexity: O(n).

Edge Cases

• If k is 1, return the single most frequent value.
• If all values appear once, any k values may be valid depending on problem constraints.
• Negative numbers work normally as dictionary keys.

class Solution {
    func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] {
        var numsCount: [Int: Int] = [:]
        for i in nums {
            if let count = numsCount[i] {
                numsCount[i] = count + 1
            } else {
                numsCount[i] = 1
            }
        }
        var countArray: [[Int]] = []
        for _ in 0...nums.count {
            countArray.append([])
        }
        for (key, value) in numsCount {
            countArray[value].append(key)
        }
        var topKElements: [Int] = []
        for i in stride(from: countArray.count - 1, to: -1, by: -1) {
            topKElements.append(contentsOf: countArray[i])
            if topKElements.count == k {
                break
            }
        }
        return topKElements
    }
}

var solution = Solution()

var testcase1 = solution.topKFrequent([1,1,1,2,2,3], 2)
print(testcase1) // [1, 2]

var testcase2 = solution.topKFrequent([1], 1)
print(testcase2) // [1]