Coding - Top K Frequent Elements

Full Interview Question: "Coding - Top K Frequent Elements" asked at Uber

Problem Statement

Given a non-empty array of integers, return the k most frequent elements.

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

• '1' appears three times.
• '2' appears twice.
• '3' appears once. So the top 2 frequent elements are [1,2]. `

Example 2: ` Input: nums = [1], k = 1 Output: [1] Explanation:

• '1' appears once. So the top 1 frequent element is [1]. `

Note:

• You may assume k is always valid, 1 ≤ k ≤ len(nums).
• It's guaranteed that the input list is non-empty, and the numbers are always integer.

Constraints

• 1 ≤ len(nums) ≤ 50000
• 0 ≤ nums[i] ≤ 100000
• 1 ≤ k ≤ len(nums)
• The numbers are always integer.

Hints

1. Try to solve the problem using a hash table.
2. Use a max heap or a min heap to find the top k elements.

Solution

Here's a Python solution using a hash table and a max heap:

`python import heapq

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

    # Create a max heap
    max_heap = [(-freq, num) for num, freq in count.items()]
    heapq.heapify(max_heap)
    
    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), where n is the length of the input array. The space complexity is O(n), as we need to store the count of each element in a hash table.