Medium
Given an integer array nums
and an integer k
, return the k
most frequent elements. You may return the answer in any order.
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Example 2:
Input: nums = [1], k = 1
Output: [1]
Constraints:
1 <= nums.length <= 105
k
is in the range [1, the number of unique elements in the array]
.Follow up: Your algorithm’s time complexity must be better than O(n log n)
, where n is the array’s size.
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;
public class Solution {
public int[] topKFrequent(int[] nums, int k) {
Arrays.sort(nums);
// Min heap of <number, frequency>
Queue<int[]> queue = new PriorityQueue<>(k + 1, (a, b) -> (a[1] - b[1]));
// Filter with min heap
int j = 0;
for (int i = 0; i <= nums.length; i++) {
if (i == nums.length || nums[i] != nums[j]) {
queue.offer(new int[] {nums[j], i - j});
if (queue.size() > k) {
queue.poll();
}
j = i;
}
}
// Convert to int array
int[] result = new int[k];
for (int i = k - 1; i >= 0; i--) {
result[i] = queue.poll()[0];
}
return result;
}
}
Time Complexity (Big O Time):
nums
array using Arrays.sort(nums)
takes O(n*log(n)), where ‘n’ is the length of the input array.queue
) to keep track of the top k frequent elements. Adding an element to the priority queue takes O(log(k)) time, and it’s done for each unique element in the input array.Considering the dominant operations, the overall time complexity of the program is O(n*log(n)) due to the sorting step.
Space Complexity (Big O Space):
queue
) to store the distinct elements along with their frequencies. The maximum size of this priority queue can be ‘k + 1’ (to ensure ‘k’ elements are retained at most).result
of size ‘k’ to store the top k frequent elements.Therefore, the overall space complexity of the program is O(k) because the priority queue dominates the space complexity, and ‘k’ is the maximum size it can have.
In summary, the provided program has a time complexity of O(n*log(n)) and a space complexity of O(k), where ‘n’ is the length of the input array, and ‘k’ is the value of ‘k’ specified as an argument.