v9.1.1
Menu

Top K Frequent Elements

mediumPROHash Maps & CountingLinkedIn DSA

Given an integer array nums and integer k, return the k most frequent elements as a list, in any order.

If several elements tie in frequency for the last of the k places, choose the one whose first occurrence in nums comes earliest.

The tests sort your list and print it space-separated (e.g. 1 2).

Example

Input
1,1,1,2,2,3
2
Output
1 2
Reasoning
  • The inputs are nums, here the six integers 1,1,1,2,2,3, and k=2k = 2, the number of elements to report.
  • The frequency of a value vv is how many positions of nums hold vv: f(1)=3f(1) = 3, f(2)=2f(2) = 2, f(3)=1f(3) = 1. The three counts add up to 66, the length of the array.
  • Ranking the distinct values by frequency from highest to lowest gives 11 (33 times), then 22 (22 times), then 33 (11 time). The top k=2k = 2 are 11 and 22; the value 33 is left out because two values already rank above it.
  • The answer is the set {1,2}\{1, 2\}, printed in ascending order as 1 2. Notice that only the distinct values matter in the output: no value is repeated, and the counts themselves are never shown.
  • Ties only matter at the cut-off: in [4,4,4,1,1,2,2,3][4, 4, 4, 1, 1, 2, 2, 3] with k=2k = 2, both 11 and 22 appear twice, and 11 wins because it shows up first, giving 1 4.

Constraints

  • 1 <= len(nums) <= 10^5
  • 1 <= k <= number of unique elements

More from LinkedIn DSA

PRO

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Test results

Sign in to run your code against the test cases.