Top K Frequent Elements

Problem Statement

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

Constraints

• 1 <= nums.length <= 10^5
• k is in the range [1, nums.length].
• The number of unique elements in the array is in the range [1, nums.length].
• nums[i] is an integer in the range [1, 10^5].

Examples

Example 1

Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2] Explanation: The most frequent elements are [1,2] as they appear 3 times and 2 times respectively. Note that [2,1] is also an acceptable answer.

Example 2

Input: nums = [4,1,-1,2,-1,2,3], k = 2 Output: [-1, 2] Explanation: The most frequent elements are [-1, 2] as they appear 3 times. Note that [-1, 2] is also an acceptable answer.

Hints

1. A frequency map can be used to store the frequency of each element.
2. A max heap or a min heap can be used to find the top k elements.
3. A bucket sort approach can be used to distribute elements into buckets based on their frequency.

Solution

Here is a possible solution using a frequency map and a max heap:

`python import heapq

def topKFrequent(nums, k): from collections import Counter # Create a frequency map freq_map = Counter(nums) # Create a max heap max_heap = [(-freq, num) for num, freq in freq_map.items()] heapq.heapify(max_heap)

# Extract the top k elements
result = []
for _ in range(k):
    result.append(heapq.heappop(max_heap)[1])

return result

`

This solution has a time complexity of O(n log k) due to the heap operations, where n is the number of elements in the input array. The space complexity is O(n) for the frequency map and the heap.