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

• We use min heap, iterate all frequency entry, pop if 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, and add() / poll() takes O(lg k) time, total takes O(n 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 have n unique elements, the maximum frequency is n. We can count the frequency of each element, then we create a bucket of size nums.size + 1, store the element value at the index [frequency] 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) {
        val value = nums[i]
        if (frequencyMap.containsKey(value)) {
            frequencyMap[value] = frequencyMap[value]!! + 1
        } else {
            frequencyMap[value] = 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<MutableList<Int>>(nums.size + 1) { _ -> mutableListOf() }
    for (entry in frequencyMap) {
        val value = entry.key
        val frequency = entry.value
        bucketList.get(frequency).add(value)
    }
    // We have to iterate all bucket item, some item might be empty list.
    for (i in bucketList.size - 1 downTo 0) {
        if (bucketList.getOrNull(i) == null) continue
        else {
            results.addAll(bucketList.get(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).
• Space Complexity: O(n).