LeetCode 347: Top K Frequent Elements Solution in Python – A Step-by-Step Guide

What Is LeetCode 347: Top K Frequent Elements?

In LeetCode 347: Top K Frequent Elements, you’re given an integer array nums and an integer k, and your task is to return the k most frequent elements in any order. For example, with nums = [1,1,1,2,2,3] and k = 2, the result could be [1,2] (1 appears 3 times, 2 appears 2 times). This problem tests your ability to handle frequency analysis efficiently, connecting to concepts in LeetCode 692: Top K Frequent Words.

Problem Statement

• Input: An integer array nums and an integer k.
• Output: A list of the k most frequent elements (in any order).
• Rules:
• Return exactly k elements.
• If multiple elements have the same frequency, any k of them are valid.
• Assume a solution exists (k ≤ unique elements).

Constraints

• 1 <= nums.length <= 10⁵
• -10⁴ <= nums[i] <= 10⁴
• 1 <= k <= number of unique elements

Examples

• Input: nums = [1,1,1,2,2,3], k = 2
• Output: [1,2] (1:3 times, 2:2 times)
• Input: nums = [1], k = 1
• Output: [1] (1:1 time)
• Input: nums = [4,1,-1,2,-1,2,3], k = 2
• Output: [-1,2] (-1:2 times, 2:2 times)

Understanding the Problem: Finding the Top K

To solve LeetCode 347: Top K Frequent Elements in Python, we need to identify the k elements with the highest frequencies in nums. A naive approach—counting frequencies and sorting all elements—is O(n log n), which can be improved. We’ll use:

• Best Solution (Heap-Based): O(n log k) time, O(n) space—fast and optimal.
• Alternative Solution (Sorting): O(n log n) time, O(n) space—clear but less efficient.

Let’s start with the heap-based solution, explained in a beginner-friendly way.

Best Solution: Heap-Based Approach

Why This Is the Best Solution

The heap-based approach is the top choice for LeetCode 347 because it’s efficient—O(n log k) time, O(n) space—and uses a min-heap to keep only the top k elements, avoiding a full sort. It leverages Python’s heapq module for simplicity and speed. It’s like picking the top contestants without sorting the entire list—smart and quick!

How It Works

Think of this as a frequency filter:

• Step 1: Count Frequencies:
• Use a hash map to count occurrences of each number.
• Step 2: Build Min-Heap:
• Push (frequency, number) pairs into a heap.
• If heap size > k, pop the smallest frequency.
• Step 3: Extract Results:
• Collect remaining heap elements (k most frequent).
• Step 4: Why It Works:
• Min-heap ensures only k highest frequencies remain.
• Heap ops are O(log k), beating full sort.

It’s like sifting out the top k with a clever sieve!

Step-by-Step Example

Example: nums = [1,1,1,2,2,3], k = 2

• Step 1: Map = {1:3, 2:2, 3:1}
• Step 2: Heap:
• Push (3,1): [(3,1)]
• Push (2,2): [(2,2), (3,1)]
• Push (1,3): [(1,3), (3,1), (2,2)], pop (1,3): [(2,2), (3,1)]
• Step 3: Extract: [2, 1] (from (2,2), (3,1))
• Result: [1, 2]

Example: nums = [4,1,-1,2,-1,2,3], k = 2

• Map: {4:1, 1:1, -1:2, 2:2, 3:1}
• Heap:
• [(1,4)], [(1,1), (1,4)], [(-1,2), (1,4)], [(-1,2), (2,2)], [(2,-1), (2,2)]
• Extract: [-1, 2]
• Result: [-1, 2]

Code with Detailed Line-by-Line Explanation

Copy codefrom collections import Counter
import heapq

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # Count frequencies
        count = Counter(nums)

        # Build min-heap of k elements
        heap = []
        for num, freq in count.items():
            heapq.heappush(heap, (freq, num))
            if len(heap) > k:
                heapq.heappop(heap)

        # Extract k elements
        return [num for freq, num in heap]

• Lines 6-7: Use Counter to count frequencies.
• Lines 10-13: Build heap:
• Push (freq, num) pairs.
• Pop smallest if size > k.
• Line 16: Extract numbers from heap.
• Time Complexity: O(n log k)—n heap insertions at O(log k) each.
• Space Complexity: O(n)—hash map and heap.

This is like a frequency-sifting pro—fast and sleek!

Alternative Solution: Sorting Approach

Why an Alternative Approach?

The sorting approach—O(n log n) time, O(n) space—counts frequencies and sorts them by frequency, then takes the top k. It’s the simplest way to understand frequency ranking but slower due to full sorting. It’s like sorting all votes before picking winners—clear but less optimal!

How It Works

Count and sort:

• Step 1: Build frequency map.
• Step 2: Sort by frequency (descending).
• Step 3: Take top k elements.

Step-by-Step Example

Example: nums = [1,1,2], k = 2

• Map: {1:2, 2:1}
• Sort: [(2,1), (1,2)]
• Top k: [1, 2]
• Result: [1, 2]

Code for Sorting Approach

Copy codefrom collections import Counter

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # Count frequencies
        count = Counter(nums)

        # Sort by frequency descending
        sorted_items = sorted(count.items(), key=lambda x: x[1], reverse=True)

        # Take top k elements
        return [item[0] for item in sorted_items[:k]]

• Time Complexity: O(n log n)—sorting dominates.
• Space Complexity: O(n)—map and sorted list.

It’s a frequency-sorting checker—vivid but heavy!

Comparing the Two Solutions

• Heap-Based (Best):
• Pros: O(n log k) time, O(n) space, fast for small k.
• Cons: Heap logic less intuitive.
• Sorting (Alternative):
• Pros: O(n log n) time, O(n) space, straightforward.
• Cons: Slower due to full sort.

Heap-based wins for efficiency.

Additional Examples and Edge Cases

• [1], 1: [1].
• [1,1,1], 1: [1].
• [2,2,3,3,3], 2: [3, 2].

Both handle these, but heap-based is faster.

Complexity Breakdown

• Heap-Based: Time O(n log k), Space O(n).
• Sorting: Time O(n log n), Space O(n).

Heap-based is the clear choice.

Key Takeaways

• Heap-Based: Sift the top—efficient!
• Sorting: Rank all—simple!
• Python: Heaps and counters shine—see [Python Basics](/python/basics).
• Frequencies: Heaps beat full sorts.

Final Thoughts: Pick the Tops

LeetCode 347: Top K Frequent Elements in Python is a frequency-counting gem. The heap-based solution offers speed and elegance, while sorting provides a tangible baseline. Want more frequency challenges? Try LeetCode 692: Top K Frequent Words or LeetCode 215: Kth Largest Element in an Array. Ready to tally? Head to Solve LeetCode 347 on LeetCode and find those top k today!