A-005● Day 052026.05.07mediumleetcode #347neetcode150

Top K Frequent Elements

#array#hash-table#divide-and-conquer#sorting#heap-priority-queue#bucket-sort#counting#quickselect

↗ leetcode #347 · top-k-frequent-elements

Problem

· problem

P.005

Top K Frequent Elements

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order. Follow up: Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

constraints

· 1 ≤ nums.length ≤ 10^5
· -10^4 ≤ nums[i] ≤ 10^4
· k is in the range [1, the number of unique elements in the array]
· The answer is guaranteed to be unique

// paraphrased summary — see source for full text

examples

example 1input → output

[1,1,1,2,2,3]
2

[1,2]

example 2input → output

[1]
1

[1]

example 3input → output

[1,2,1,2,1,2,3,1,3,2]
2

[1,2]

Pre-solve

· pre-solve

● 1list shown→● 2select→● 3reveal

☐
Does the order of returned elements matter?
☐
Can the array contain negative numbers?
☐
Is k always less than or equal to the number of unique elements?
☐
Should we return the k least frequent elements?
☐
Do we need to distinguish duplicate values as separate elements?

check the items you would ask, then press confirm

// session-only state — refresh resets (repeatable practice)

Logic Structure

· logic

● 1slots shown→● 2pick per slot→● 3reveal

// pick one code line per slot to assemble the algorithm flow. no typing — just the logic skeleton.

step 1· Initialize frequency counter

○

count = {}

○

count = []

○

count = set()

step 2· Initialize frequency bucket array

○

freq = [[] for i in range(len(nums) + 1)]

○

freq = [[] for i in range(len(nums))]

○

freq = {}

step 3· Count frequencies by iterating array│ nested

○

count[n] = 1 + count.get(n, 0)

○

count[n] = count.get(n, 1) + 1

○

count[n] += 1

step 4· Add elements to frequency buckets│ nested

○

freq[c].append(n)

○

freq[n].append(c)

○

freq[c] = n

step 5· Iterate from highest to lowest frequency and collect

○

for i in range(len(freq) - 1, 0, -1):

○

for i in range(len(freq)):

○

for i in range(len(freq) - 1, -1, -1):

pick one option per slot

// format: slot — recursive / DP patterns use ordering / state-first formats. ADR-08 follow-up.

Solve · Trace

· solve

solution.py

class Solution:

    def topKFrequent(self, nums: List[int], k: int) -> List[int]:

        count = {}

        freq = [[] for i in range(len(nums) + 1)]

        for n in nums:

            count[n] = 1 + count.get(n, 0)

        for n, c in count.items():

            freq[c].append(n)

        res = []

        for i in range(len(freq) - 1, 0, -1):

            res += freq[i]

            if len(res) == k:

                return res

        # O(n)

mental dry-run cases

// walk each case in your head; expand the worked example below if stuck.

case 1

[1,1,1,2,2,3]
2

→

[1,2]

case 2

[1]
1

→

[1]

case 3

[1,2,1,2,1,2,3,1,3,2]
2

→

[1,2]

// UI does not walk-through — you do the dry-run mentally. Expand the worked example if stuck.