Top K Frequent Elements Using Heap in DSA Rust - Time & Space Complexity

Time Complexity: Top K Frequent Elements Using Heap

O(n + m log m)

Understanding Time Complexity

We want to understand how long it takes to find the top K frequent elements in a list using a heap.

How does the time needed grow as the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

use std::collections::{HashMap, BinaryHeap};

fn top_k_frequent(nums: Vec<i32>, k: usize) -> Vec<i32> {
    let mut freq_map = HashMap::new();
    for num in nums {
        *freq_map.entry(num).or_insert(0) += 1;
    }
    let mut heap = BinaryHeap::new();
    for (&num, &count) in &freq_map {
        heap.push((count, num));
    }
    let mut result = Vec::new();
    for _ in 0..k {
        if let Some((_, num)) = heap.pop() {
            result.push(num);
        }
    }
    result
}

This code counts how often each number appears, then uses a heap to find the top K numbers with the highest counts.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Loop over all numbers to count frequencies, then loop over unique numbers to build the heap, and finally pop K times from the heap.
• How many times: Counting loop runs n times (n = length of input), heap building runs m times (m = number of unique elements), popping runs k times.

How Execution Grows With Input

As the input list grows, counting frequencies grows linearly with n. Building the heap depends on m, the unique elements, which can be up to n in worst case. Popping k times grows with k, usually smaller than n.

Input Size (n)	Approx. Operations
10	~10 (count) + ~10 (heap build) + k pops
100	~100 (count) + ~100 (heap build) + k pops
1000	~1000 (count) + ~1000 (heap build) + k pops

Pattern observation: Counting grows directly with input size, heap operations grow with unique elements, and popping grows with k.

Final Time Complexity

Time Complexity: O(n + m log m)

This means the time grows linearly with input size n for counting, plus m log m for heap operations where m is unique elements.

Common Mistake

[X] Wrong: "The time is just O(n) because we only loop over the input once."

[OK] Correct: Counting is O(n), but building and popping from the heap depends on unique elements and involves log m operations, which can add up.

Interview Connect

Understanding how counting and heap operations combine helps you explain your solution clearly and shows you know how to analyze mixed steps in algorithms.

Self-Check

"What if we used a min-heap of size k instead of pushing all elements into a max-heap? How would the time complexity change?"

Practice

1. What is the main purpose of using a heap in the Top K Frequent Elements problem?

easy

A. To efficiently keep track of the top K elements by frequency

B. To sort all elements in ascending order

C. To store elements without any order

D. To remove duplicates from the list

Solution

1. Step 1: Understand the problem goal

   The goal is to find the K elements that appear most frequently in a list.

2. Step 2: Role of heap in this context

   A heap helps efficiently keep track of the top K frequent elements by maintaining a small structure that updates as we process frequencies.

3. Final Answer:

   To efficiently keep track of the top K elements by frequency -> Option A

4. Quick Check:

   Heap = Efficient top K tracking [OK]

Hint: Heap keeps top K elements efficiently by frequency [OK]

Common Mistakes:

• Thinking heap sorts all elements fully
• Confusing heap with simple list storage
• Assuming heap removes duplicates

2. Which Rust data structure is best suited to store frequencies of elements before using a heap?

easy

A. Vec<T>

B. HashMap

C. LinkedList<T>

D. BinaryHeap<T>

Solution

1. Step 1: Identify frequency storage needs

   We need to count how many times each element appears, so we need a key-value structure.

2. Step 2: Choose appropriate Rust structure

   HashMap stores elements as keys and their counts as values efficiently.

3. Final Answer:

   HashMap<T, usize> -> Option B

4. Quick Check:

   Frequency storage = HashMap [OK]

Hint: Use HashMap to count frequencies before heap [OK]

Common Mistakes:

• Using Vec which is not key-value
• Using LinkedList which is inefficient here
• Confusing BinaryHeap with frequency map

3. What is the output of this Rust code snippet?

use std::collections::{BinaryHeap, HashMap};

fn top_k_frequent(nums: Vec<i32>, k: usize) -> Vec<i32> {
    let mut freq = HashMap::new();
    for num in nums {
        *freq.entry(num).or_insert(0) += 1;
    }
    let mut heap = BinaryHeap::new();
    for (&num, &count) in &freq {
        heap.push((count, num));
    }
    let mut result = Vec::new();
    for _ in 0..k {
        if let Some((_, num)) = heap.pop() {
            result.push(num);
        }
    }
    result
}

fn main() {
    let nums = vec![1,1,1,2,2,3];
    let k = 2;
    let top = top_k_frequent(nums, k);
    println!("{:?}", top);
}

medium

A. [2, 1]

B. [3, 2]

C. [1, 2]

D. [1, 3]

Solution

1. Step 1: Count frequencies

   1 appears 3 times, 2 appears 2 times, 3 appears 1 time.

2. Step 2: Push into max heap and pop top k

   Heap stores (count, num). Popping twice gives (3,1) then (2,2), so result is [1, 2].

3. Final Answer:

   [1, 2] -> Option C

4. Quick Check:

   Top 2 frequent = [1, 2] [OK]

Hint: Heap pops highest frequency first [OK]

Common Mistakes:

• Confusing order of output elements
• Ignoring frequency counts
• Assuming heap sorts by element value

4. Identify the bug in this Rust code for top K frequent elements:

use std::collections::{BinaryHeap, HashMap};

fn top_k_frequent(nums: Vec<i32>, k: usize) -> Vec<i32> {
    let mut freq = HashMap::new();
    for num in nums {
        freq.insert(num, freq.get(&num).unwrap_or(&0) + 1);
    }
    let mut heap = BinaryHeap::new();
    for (&num, &count) in &freq {
        heap.push((count, num));
    }
    let mut result = Vec::new();
    for _ in 0..k {
        if let Some((_, num)) = heap.pop() {
            result.push(num);
        }
    }
    result
}

medium

A. Using freq.insert overwrites counts incorrectly

B. BinaryHeap cannot store tuples

C. Loop range 0..k is invalid

D. Result vector is not returned

Solution

1. Step 1: Analyze frequency counting

   Using freq.insert(num, freq.get(&num).unwrap_or(&0) + 1) overwrites previous counts without incrementing properly.

2. Step 2: Correct frequency update method

   Should use *freq.entry(num).or_insert(0) += 1; to increment counts correctly.

3. Final Answer:

   Using freq.insert overwrites counts incorrectly -> Option A

4. Quick Check:

   Incorrect freq update = Bug [OK]

Hint: Use entry().or_insert() to increment counts safely [OK]

Common Mistakes:

• Using insert instead of entry for counting
• Assuming BinaryHeap can't store tuples
• Ignoring return of result vector

5. Given a large list with many elements having the same frequency, how can you modify the heap approach to ensure the top K frequent elements are returned in ascending order of their values when frequencies tie?

hard

A. Use a min-heap with (frequency, -element) pairs

B. Use a max-heap with (frequency, element) pairs and reverse result after extraction

C. Use a max-heap with (frequency, Reverse(element)) pairs

D. Use a max-heap with (frequency, element) pairs and sort result by element ascending after extraction

Solution

1. Step 1: Understand tie-breaking need

   When frequencies tie, elements should be ordered ascending by their value in final output.

2. Step 2: Heap stores by frequency only

   Heap orders by frequency, but does not guarantee order among ties, so sorting result after extraction is needed.

3. Step 3: Sort extracted top K by element ascending

   After popping top K from heap, sort the result vector by element ascending to meet tie-break condition.

4. Final Answer:

   Use a max-heap with (frequency, element) pairs and sort result by element ascending after extraction -> Option D

5. Quick Check:

   Sort after heap extraction for tie-break [OK]

Hint: Sort top K result by element ascending after heap extraction [OK]

Common Mistakes:

• Trying to encode tie-break in heap key incorrectly
• Using negative values causing confusion
• Not sorting result after extraction