Top K Frequent Elements
Medium About 20 min Free, no account needed
Return the k most frequent values, most frequent first.
The brief
Given an integer array nums and an integer k, return the k most frequent
values, ordered by descending frequency; break frequency ties by the
smaller value first.
knever exceeds the number of distinct values.
The obvious approach recounts every element's frequency with a nested scan, O(n2)
before it even starts picking winners. The hidden test runs on 200,000
elements, so it's too slow. You need to count frequencies in linear time, then
select the top k by (frequency desc, value asc) without rescanning.
Starter code
using System;
public class Solution
{
// TODO: return the k most frequent values: frequency desc, ties by smaller value first.
public int[] TopKFrequent(int[] nums, int k)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
Related guides
What it practices
- Hash maps and sets
- Trade memory for constant-time lookups, membership tests and frequency counts.
- Heaps and priority queues
- Pull the smallest or largest pending item cheaply for top-k, scheduling and eviction.
Related katas
- Contiguous Array Medium Free Longest subarray holding as many zeros as ones.
- Degree of an Array Medium Free Find the shortest contiguous slice whose most-frequent-element count matches the whole array.
- Find All Anagram Start Indices Medium Free Every position where an anagram of the pattern begins.
- Count Quadruples Summing to Target Medium Free Count index quadruples that sum to a target - without the quadruple loop.