MediumCoding

Top k frequent elements

Asked at

Amazon

Apple

Meta

SAP

Oracle

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

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

Your solution must run in better than O(n log n) time, where n = nums.length.

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

**Input: **nums = [4,4,6,6,7], k = 2 Output: [4,6] Explanation: 4 and 6 both occur twice (highest), 7 occurs once.

Input: nums = [-1,-1,-2,-2,-2,-3], k = 1

1 ≤ nums.length ≤ 105
-104 ≤ nums[i] ≤ 104
1 ≤ k ≤ number of distinct elements in nums
The answer is guaranteed to be unique.

cpp

class Solution {
public:
    vector<int> topKFrequent(const vector<int>& nums, int k) {
        // Your code goes here
    }
};

java

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // Your code goes here
    }
}

python

class Solution:
    def topKFrequent(self, nums, k):
        # Your code goes here

javascript

class Solution {
  topKFrequent(nums, k) {
    // Your code goes here
  }
}

csharp

class Solution
{
    public IList<int> TopKFrequent(int[] nums, int k)
    {
        // Your code goes here
    }
}

func topKFrequent(nums []int, k int) []int {
	// Your code goes here
}

Solve on LeetCode →

Stuck? Show a way to structure it+

01Count each value's frequency.
02Place values by frequency in buckets or use a size-k heap.
03Read largest frequencies until k values are collected.
04State why the chosen method meets the bound.

Reference answer

Count values in a hash map. Because a frequency is at most n, create buckets indexed by frequency, append each value to its bucket, then scan buckets from n down until collecting k values. That is O(n) expected time and O(n) space. A min-heap of size k is O(n log k) and is useful for a stream. Sorting all distinct values is O(n log n) and misses the stated better-than-full-sort target. In an interview, make the invariant explicit before writing code, trace a boundary example that breaks a tempting shortcut, state what each stored value represents, and explain why every update preserves correctness. This verification step also surfaces empty-input, duplicate-value, and numeric-limit cases.

Then expect these follow-ups

How would you maintain the top k in a live stream?
Tests: heap maintenance
How do ties affect output when uniqueness is not guaranteed?
Tests: specification

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question