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

Hiring now

Get the Amazon interview, not just the prep

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Or practice this question first

Next question