Brute Force Solution

A naive approach involves counting the frequency of each element in the array and then sorting the elements based on their frequencies. We can then select the top k elements.

1. Count Frequencies: Iterate through the array and store the frequency of each element in a hash map (dictionary).
2. Sort by Frequency: Sort the elements of the hash map based on their frequencies in descending order.
3. Select Top k: Return the first k elements from the sorted list.

Code Example (Python):

def topKFrequent_brute_force(nums, k):
    freq_map = {}
    for num in nums:
        freq_map[num] = freq_map.get(num, 0) + 1

    sorted_nums = sorted(freq_map.items(), key=lambda x: x[1], reverse=True)

    result = [num for num, freq in sorted_nums[:k]]
    return result

Time Complexity: O(n log n), where n is the number of elements in the array. This is due to the sorting step.

Space Complexity: O(n), where n is the number of unique elements in the array, as we store the frequencies in a hash map.

Optimal Solution (Using a Heap)

An efficient solution can be achieved using a min-heap (priority queue). We maintain a heap of size k that stores the k most frequent elements seen so far. For each new element, we compare its frequency with the minimum frequency in the heap. If the new element's frequency is greater, we replace the element with the minimum frequency in the heap with the new element.

1. Count Frequencies: Same as the brute force approach.
2. Heapify: Build a min-heap of size k with elements from the frequency map. The heap will be ordered by frequency.
3. Iterate and Adjust: Iterate through the remaining elements in the frequency map. If an element's frequency is greater than the root of the min-heap, replace the root with the element and heapify the min-heap.
4. Extract Result: The elements remaining in the min-heap are the k most frequent elements. Extract them from the heap.

Code Example (Python):

import heapq

def topKFrequent(nums, k):
    freq_map = {}
    for num in nums:
        freq_map[num] = freq_map.get(num, 0) + 1

    heap = []
    for num, freq in freq_map.items():
        if len(heap) < k:
            heapq.heappush(heap, (freq, num))
        elif freq > heap[0][0]:
            heapq.heapreplace(heap, (freq, num))

    result = [num for freq, num in heap]
    return result

Time Complexity: O(n log k), where n is the number of elements in the array. Building the frequency map takes O(n) time. Iterating through the frequency map and heapifying takes O(n log k) time. If k is close to n, time complexity becomes O(n log n).

Space Complexity: O(n), where n is the number of unique elements in the array. This is for storing the frequency map.

Edge Cases

• Empty Array: If the input array nums is empty, return an empty list.
• k = 0: If k is 0, return an empty list.
• k > Number of Unique Elements: If k is greater than the number of unique elements, return all unique elements.
• All Elements are Same: If all elements are the same, return the element.