Week 1 · Arrays & Hashing

Top K Frequent Elements

Return the k values that occur most frequently. The pattern is count first, then select by frequency.

Medium Arrays & Hashing Week 1 Practice runner

Frame the problem

The answer may be returned in any order.
Values can be negative or positive.
k is based on distinct values, not total array length.

1. Reveal example inputs and outputs

Example 1

Input:

top_k_frequent([
  1,
  1,
  1,
  2,
  2,
  3
], 2)

Output:

[
  1,
  2
]

Example 2

Input:

top_k_frequent([
  1
], 1)

Output:

[
  1
]

2. Brute force first

What would it cost to count each value by scanning the array repeatedly? How does a frequency map remove that repeated scan?

3. Reveal the insight ladder

Build a value-to-count map.
Select the k largest counts with a heap, bucket array, or sorting.
For interview clarity, sorting counts is acceptable unless the interviewer asks for O(n).

4. Dry run before code

nums = [1, 1, 1, 2, 2, 3], k = 2.
Counts are {1: 3, 2: 2, 3: 1}.
The two highest-frequency values are 1 and 2.

5. Reveal final Python solution

from collections import Counter

def top_k_frequent(nums, k):
    counts = Counter(nums)
    return [value for value, _ in counts.most_common(k)]

Complexity: Counter plus sorting-like selection is O(n log u) in the simple version, where u is distinct values. Bucket selection can be O(n).

Interview narration

I separate counting from selection.
The output is values, not counts.
If the interviewer wants linear time, I can bucket values by frequency.

Common traps

Returning counts instead of values.
Forgetting that output order is usually irrelevant.
Using k against the raw list rather than distinct values.

Follow-up drills

1. How would you make it O(n)?

Create buckets indexed by frequency from 0 to n, place each value in its frequency bucket, then walk buckets from high to low until k values are collected.

2. How would you handle a stream?

Maintain counts and a heap or ordered structure if you need repeated top-k queries. For one final query, a counter remains enough.

Interactive runner

Write the required Python function. Your code runs locally in this browser. Hints reveal one failing case at a time.