347.top-k-frequent-elements.md

347. Top K Frequent Elements

Clarification Questions

• Is the input array sorted?
• Is the top k frequent elements unique?
• Is k always valid? In the range of 1 and number of unique elements?

Test Cases

Normal Cases

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

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

Edge / Corner Cases

• Multiple answers. (Not gonna happen, it is guaranteed that the answer is unique.)

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

Heap

To find the top k frequent elements, we use a fixed-size k min heap, iterate all frequency entry, pop when the heap size > k, the final result of heap will be the result (in reversed order).

fun topKFrequent(nums: IntArray, k: Int): IntArray {
    val frequencyMap = hashMapOf<Int, Int>()
    for (num in nums) {
        frequencyMap[num] = (frequencyMap[num] ?: 0) + 1
    }
    
    val minHeap = PriorityQueue<Int>() { n1, n2 -> frequencyMap[n1]!! - frequencyMap[n2]!! }
    for (key in frequencyMap.keys) {
        minHeap.add(key)
        if (minHeap.size > k) {
            minHeap.poll()
        }
    }
    val results = IntArray(k)
    for (i in k - 1 downTo 0) {
        results[i] = minHeap.poll()
    }
    return results
}

• Time Complexity: O(n lg k)
  • We iterate n items.
  • add() / poll() takes O(lg k) time.
• Space Complexity: O(n) + O(k)
  • For hash table and heap respectively, total takes O(n) time.

Bucket Sort

We have size n, and we might have n unique elements in worst case, the maximum frequency is n. We can count the frequency of each element, then we create a bucket of size nums.size + 1 (1-based), store the element value at the index [frequency] in the bucket, i.e. if value A has frequency 2, we store A at index 2 in the bucket.

nums = [1,2,3,4,1,2,2,3,3,3]
frequency = {
    1: 2,
    2: 3,
    3: 4,
    4: 1
}

bucket = [
    [],     // 0 frequency
    [4],    // 1 frequency, which is 4
    [1],    // 2 frequency, which is 1
    [2],    // 3 frequency, which is 2
    [3]     // 4 frequency, which is 3
]

// Or
nums = [1,1,1,1]
frequency = {
    1: 4
}
bucket = [
    [],     // 0 frequency
    [],     // 1 frequency
    [],     // 2 frequency
    [],     // 3 frequency
    [1]     // 4 frequency, which is 1
]

Then we iterate the bucket from the end to the start, and add the value to the result list.

fun topKFrequent(nums: IntArray, k: Int): IntArray {
    val results = mutableListOf<Int>()
    // Value and its frequency
    // (1, 3)
    // (2, 2)
    // (3, 3)
    // (4, 1)
    val frequencyMap = hashMapOf<Int, Int>()
    for (i in 0 until nums.size) {
        frequencyMap[nums[i]] = (frequencyMap[nums[i]] ?: 0) + 1
    }

    // We use frequency as index, and store its values of that frequency
    // bucketList[0] = []
    // bucketList[1] = [4]
    // bucketList[2] = [2]
    // bucketList[3] = [1, 3]
    // bucketList[4] = []
    // Plus 1 for zero frequency
    val bucketList = Array(n + 1) { mutableListOf<Int>() }
    for ((k, v) in frequencyMap) {
        // Use frequency as index, and store its values of that frequency
        bucketList[v].add(k)
    }
    // We have to iterate all bucket item in reverse order (finding top k)
    for (i in bucketList.size - 1 downTo 1) {
        results.addAll(bucketList[i])
        // The answer guaranteed to be unique, so we can break the loop when we have enough k elements.
        if (results.size >= k) break
    }
    return results.toIntArray()
}

• Time Complexity: O(n)
  • We iterate n items and n items in bucket list.
• Space Complexity: O(n)
  • For hash table and bucket list respectively, total takes O(n) time.