LeetCode-in-All

347. Top K Frequent Elements

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
• -104 <= nums[i] <= 104
• k is in the range [1, the number of unique elements in the array].
• It is guaranteed that the answer is unique.

Follow up: Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.

Solution

-spec top_k_frequent(Nums :: [integer()], K :: integer()) -> [integer()].
top_k_frequent(Nums, K) ->
    % Count frequencies using a map
    FreqMap = lists:foldl(
        fun(N, Map) ->
            maps:update_with(N, fun(V) -> V + 1 end, 1, Map)
        end,
        #{},
        Nums
    ),
    
    % Convert map to list, sort by frequency (descending), take K elements
    FreqList = maps:to_list(FreqMap),
    SortedList = lists:sort(
        fun({_, Count1}, {_, Count2}) -> Count1 > Count2 end,
        FreqList
    ),
    TopK = lists:sublist(SortedList, K),
    
    % Extract only the numbers from the result
    [Num || {Num, _Count} <- TopK].

This site is open source. Improve this page.