Practice/Amazon/Leetcode 347. Top K Frequent Elements

Leetcode 347. Top K Frequent Elements

CodingMust

Problem

You are given an array of integers nums and an integer k. Your task is to identify and return the k elements that appear most frequently in the array.

The order of elements in your output does not matter. You may assume that the answer is guaranteed to be unique (there will always be exactly k elements with the highest frequencies).

Your solution should be more efficient than sorting the entire array by frequency, which would take O(n log n) time.

Requirements

1. Count the frequency of each element in the input array
2. Identify the k elements with the highest occurrence counts
3. Return these k elements in any order
4. Achieve better time complexity than O(n log n)

Constraints

• 1 ≤ nums.length ≤ 10^5
• -10^4 ≤ nums[i] ≤ 10^4
• k is in the range [1, number of unique elements in nums]
• The answer is guaranteed to be unique
• Target time complexity: O(n log k) or better
• Target space complexity: O(n)

Examples

Example 1:

Input: nums = [1, 1, 1, 2, 2, 3], k = 2 Output: [1, 2] Explanation: The element 1 appears 3 times, element 2 appears 2 times, and element 3 appears once. The two most frequent elements are 1 and 2.

Example 2:

Input: nums = [1], k = 1 Output: [1] Explanation: There is only one element, which is automatically the most frequent.

Example 3:

Input: nums = [4, 5, 6], k = 2 Output: [4, 5] (or any combination of 2 elements) Explanation: All elements appear exactly once. Any 2 of the 3 elements form a valid answer.