Question

LeetCode Link | 347. Top K Frequent Elements | Medium

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Follow up: Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.

Constrains

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4
  • k is in the range [1, the number of unique elements in the array].
  • It is guaranteed that the answer is unique.

Examples

Example 1

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

Example 2

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

Solution Approach

Method: Min Heap

Constrains

  • None

This method does not have any limitations.

Concept Explanation

This problem mainly involves three key tasks:

  1. Counting element frequency:
    • This can be done using a map to keep track of the frequency of each element.
  2. Sorting by frequency:
    • A priority queue (a container adapter) is suitable for this task.
  3. Finding the top K frequent elements:
    • After counting the frequency, we use the priority queue to sort the frequencies and extract the top K elements.

Priority Queue Explanation

A priority queue is essentially a heap dressed up as a queue. It provides an interface that only allows elements to be added at the back and removed from the front, making it look like a queue.

Internally, the priority queue arranges elements based on their priority. By default, priority_queue uses a max-heap (a complete binary tree represented as a vector) to sort elements.

Heap Definition

A heap is a complete binary tree where each node’s value is not less than (max-heap) or not greater than (min-heap) its children’s values. In a max-heap, the root is the largest element, while in a min-heap, the root is the smallest element.

Usage in This Problem

For this problem, we use a priority queue to sort part of the frequencies.

  • Why not use quicksort? Using quicksort would require converting the map to a vector and sorting the entire array, which is inefficient for this scenario where we only need to maintain a sequence of the top K elements. Thus, a priority queue is optimal.

Choosing Between Min-Heap and Max-Heap

  • Min-Heap: Suitable because we need to keep the largest K elements.
  • Max-Heap: If used, we would remove the largest element on each pop operation, which is not suitable for maintaining the top K elements.

Steps:

  1. Count frequencies using a map.
  2. Use a min-heap priority queue to store elements by frequency:
    • For each element, add it to the priority queue.
    • If the size of the queue exceeds K, remove the smallest element.
  3. After processing all elements, the priority queue will contain the top K frequent elements.

This approach ensures that only the K highest frequencies are maintained efficiently.

Code

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

TypeScript

Use map only

  • Time complexity: O(n log(n))
  • Space complexity: O(n)
1
2
3
4
5
6
7
8
9
10
11
12
function topKFrequent(nums: number[], k: number): number[] {
  const countMap: Map<number, number> = new Map<number, number>();
  // Count frequence of each element
  for (num of nums) {
    countMap.set(num, (countMap.get(num) || 0) + 1);
  }
  // Sort to the most frequent and return first k element
  return [...countMap.entries()]
  	.sort((a, b) => b[1] - a[1])
  	.slice(0, k)
  	.map(i => i[0]);
}

Use map with Min Heap

  • Time complexity: O(n log(k))
  • Space complexity: O(n + k)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
function topKFrequent(nums: number[], k: number): number[] {
	class Heap<T> {
		private readonly queue: T[];
		private readonly maxSize: number;
		private readonly compareFn: (a: T, b: T) => number;

		constructor(compareFn: (a: T, b: T) => number, maxSize: number = Infinity) {
			this.queue = [];
			this.maxSize = maxSize;
			this.compareFn = compareFn;
		}

		private compare(indexA: number, indexB: number): number {
			if (this.queue[indexA] === undefined) return 1;
			if (this.queue[indexB] === undefined) return -1;
			return this.compareFn(this.queue[indexA], this.queue[indexB]);
		}

		private swap(i: number, j: number): void {
			[this.queue[i], this.queue[j]] = [this.queue[j], this.queue[i]];
		}

		public push(num: T): void {
			this.queue.push(num);

			let index: number = this.size() - 1;
			let parent: number = Math.floor((index - 1) / 2);
			while (parent >= 0 && this.compare(parent, index) > 0) {
				this.swap(parent, index);
				index = parent;
				parent = Math.floor((index - 1) / 2);
			}

			if (heap.size() > this.maxSize) {
				heap.pop();
			}
		}

		public pop(): T {
			const out: T = this.queue[0];

			this.queue[0] = this.queue.pop();

			let index: number = 0;
			let left: number = 1;
			let child: number = this.compare(left, left + 1) > 0 ? left + 1 : left;
			while (child !== undefined && this.compare(index, child) > 0) {
				this.swap(index, child);
				index = child;
				left = 2 * index + 1;
				child = this.compare(left, left + 1) > 0 ? left + 1 : left;
			}

			return out;
		}

		public size(): number {
			return this.queue.length;
		}
	}

	// Create a map to store the frequency of each number
	const map: Map<number, number> = new Map<number, number>();
	for (const num of nums) {
		map.set(num, (map.get(num) || 0) + 1);
	}
	
	// Create a min heap to store the k most frequent elements
	const heap: Heap<[number, number]> = new Heap<[number, number]>(
		(a, b) => a[1] - b[1], 
		k
	);
	
	// Push the map entries to the heap
	for (const entry of map.entries()) {
		heap.push(entry);
	}
	
	// Pop the heap and store the result in reverse order
	const res: number[] = [];
	for (let i = heap.size() - 1; i >= 0; i--) {
		res[i] = heap.pop()[0];
	}

	return res;
};

Conclusion

Since JavaScript / TypeScript does not provide heap / priority queue, you have to implement in hand if you want to use it. But keep in mind:

The comparison function in the Heap class and the sort function in JavaScript work in opposite ways due to the nature of their operations.

In the Heap class, the comparison function is used to maintain the heap property. In a min-heap, the parent node should be smaller than its children, and in a max-heap, the parent node should be larger than its children. Therefore, when the comparison function returns a positive value, it indicates that the parent node is larger than the child node, and a swap operation is needed to restore the heap property.

On the other hand, the sort function in JavaScript sorts an array in place. When the comparison function returns a positive value, it means that the first argument should come after the second argument in the sorted sequence. Therefore, the comparison function for sort should return a negative value when the first argument is smaller than the second argument to ensure that smaller values come before larger values in the sorted array.

In summary, the comparison function in the Heap class and the sort function in JavaScript have opposite behaviors because they are used for different purposes: maintaining the heap property in a heap data structure and sorting an array, respectively.