Frequency Stack (Max Frequency First)

▶

Steps

setup

Initialize Frequency Stack

Initialize frequency map, heap array, and timestamp counter to empty or zero before any operations.

💡 Starting with empty structures ensures no residual data affects the algorithm.

Line:

self.freq = {}
self.heap = []
self.time = 0

💡 The algorithm uses these data structures to track frequencies and order pushes by time.

insert

Push 5: Increase frequency and add to heap

Push value 5: frequency of 5 becomes 1, timestamp increments to 1, push (-1, -1, 5) into heap.

💡 Each push updates frequency and timestamp to prioritize elements correctly in the heap.

Line:

self.freq[val] = self.freq.get(val, 0) + 1
self.time += 1
heapq.heappush(self.heap, (-self.freq[val], -self.time, val))

💡 The heap now contains one element with frequency 1 and timestamp 1, representing the first push.

insert

Push 7: Increase frequency and add to heap

Push value 7: frequency of 7 becomes 1, timestamp increments to 2, push (-1, -2, 7) into heap.

💡 New element 7 has same frequency as 5 but later timestamp, so it will be ordered accordingly in the heap.

Line:

self.freq[val] = self.freq.get(val, 0) + 1
self.time += 1
heapq.heappush(self.heap, (-self.freq[val], -self.time, val))

💡 Heap now contains two elements with frequency 1 but different timestamps; heap order reflects max frequency and recency.

insert

Push 5 again: Increase frequency and add to heap

Push value 5 again: frequency of 5 becomes 2, timestamp increments to 3, push (-2, -3, 5) into heap.

💡 Frequency of 5 increases, so it now has higher priority than 7 despite timestamp.

Line:

self.freq[val] = self.freq.get(val, 0) + 1
self.time += 1
heapq.heappush(self.heap, (-self.freq[val], -self.time, val))

💡 Heap root updates to the new entry with frequency 2, showing frequency dominates timestamp.

insert

Push 7 again: Increase frequency and add to heap

Push value 7 again: frequency of 7 becomes 2, timestamp increments to 4, push (-2, -4, 7) into heap.

💡 7 now matches 5 in frequency but has more recent timestamp, so it will be ordered accordingly.

Line:

self.freq[val] = self.freq.get(val, 0) + 1
self.time += 1
heapq.heappush(self.heap, (-self.freq[val], -self.time, val))

💡 Heap reorders so that the element with frequency 2 and latest timestamp is at root.

insert

Push 4: Increase frequency and add to heap

Push value 4: frequency of 4 becomes 1, timestamp increments to 5, push (-1, -5, 4) into heap.

💡 New element 4 has frequency 1, less than current max frequency 2 elements.

Line:

self.freq[val] = self.freq.get(val, 0) + 1
self.time += 1
heapq.heappush(self.heap, (-self.freq[val], -self.time, val))

💡 Heap root remains the element with frequency 2 and latest timestamp.

insert

Push 5 again: Increase frequency and add to heap

Push value 5 again: frequency of 5 becomes 3, timestamp increments to 6, push (-3, -6, 5) into heap.

💡 Frequency of 5 now exceeds all others, so it will become the root of the heap.

Line:

self.freq[val] = self.freq.get(val, 0) + 1
self.time += 1
heapq.heappush(self.heap, (-self.freq[val], -self.time, val))

💡 Heap root updates to the new highest frequency element 5 with timestamp 6.

delete

Pop: Remove element with highest frequency and most recent timestamp

Pop from heap: remove root (-3, -6, 5), decrement frequency of 5 to 2, return 5.

💡 Pop returns the element with highest frequency and most recent push, updating frequency map accordingly.

Line:

freq, time, val = heapq.heappop(self.heap)
self.freq[val] -= 1
if self.freq[val] == 0:
    del self.freq[val]
return val

💡 Pop removes the top priority element and updates frequency for future operations.

delete

Pop: Remove next highest frequency element

Pop from heap: remove root (-2, -4, 7), decrement frequency of 7 to 1, return 7.

💡 Next pop returns element with frequency 2 and latest timestamp 4, which is 7.

Line:

freq, time, val = heapq.heappop(self.heap)
self.freq[val] -= 1
if self.freq[val] == 0:
    del self.freq[val]
return val

💡 Pop respects updated frequencies and timestamps after previous operations.

delete

Pop: Remove element with frequency 2 and next recent timestamp

Pop from heap: remove root (-2, -3, 5), decrement frequency of 5 to 1, return 5.

💡 5 still has frequency 2 after previous pop, so it is next to be popped.

Line:

freq, time, val = heapq.heappop(self.heap)
self.freq[val] -= 1
if self.freq[val] == 0:
    del self.freq[val]
return val

💡 Frequency and timestamp ordering continues to determine pop order.

delete

Pop: Remove element with frequency 1 and most recent timestamp

Pop from heap: remove root (-1, -5, 4), decrement frequency of 4 to 0 and remove from freq map, return 4.

💡 4 has frequency 1 and latest timestamp among frequency 1 elements, so it is popped last.

Line:

freq, time, val = heapq.heappop(self.heap)
self.freq[val] -= 1
if self.freq[val] == 0:
    del self.freq[val]
return val

💡 Pop removes elements with frequency 1 in order of recency.

import heapq

class FreqStack:
    def __init__(self):
        self.freq = {}  # STEP 1
        self.heap = []  # STEP 1
        self.time = 0  # STEP 1

    def push(self, val: int) -> None:
        self.freq[val] = self.freq.get(val, 0) + 1  # STEP 2,3,4,5,6,7
        self.time += 1  # STEP 2,3,4,5,6,7
        heapq.heappush(self.heap, (-self.freq[val], -self.time, val))  # STEP 2,3,4,5,6,7

    def pop(self) -> int:
        freq, time, val = heapq.heappop(self.heap)  # STEP 8,9,10,11
        self.freq[val] -= 1  # STEP 8,9,10,11
        if self.freq[val] == 0:  # STEP 11
            del self.freq[val]  # STEP 11
        return val  # STEP 8,9,10,11

if __name__ == '__main__':
    fs = FreqStack()
    fs.push(5)  # STEP 2
    fs.push(7)  # STEP 3
    fs.push(5)  # STEP 4
    fs.push(7)  # STEP 5
    fs.push(4)  # STEP 6
    fs.push(5)  # STEP 7
    print(fs.pop())  # STEP 8
    print(fs.pop())  # STEP 9
    print(fs.pop())  # STEP 10
    print(fs.pop())  # STEP 11

📊

Frequency Stack (Max Frequency First) - Watch the Algorithm Execute, Step by Step

Watching each push and pop operation visually reveals how frequency and recency combine to determine the element returned by pop, which is hard to grasp from code alone.

setupmax-heap

empty heap

insertmax-heap

-1,-1,5

0

insertmax-heapswap [0↔1]

-1,-2,7

0

-1,-1,5

1

insertmax-heap

-2,-3,5

0

-1,-1,5

1

-1,-2,7

2

insertmax-heapswap [0↔1]

-2,-4,7

0

-2,-3,5

1

-1,-2,7

2

-1,-1,5

3

insertmax-heap

-2,-4,7

0

-2,-3,5

1

-1,-2,7

2

-1,-1,5

3

-1,-5,4

4

insertmax-heapswap [0↔1]

-3,-6,5

0

-2,-4,7

1

-1,-2,7

2

-1,-1,5

3

-1,-5,4

4

-2,-3,5

5

extract_maxmax-heapswap [0↔4]

-2,-4,7

0

-2,-3,5

1

-1,-2,7

2

-1,-1,5

3

-1,-5,4

4

Added: 5

extract_maxmax-heapswap [0↔3]

-2,-3,5

0

-1,-5,4

1

-1,-2,7

2

-1,-1,5

3

Added: 7

extract_maxmax-heapswap [0↔2]

-1,-5,4

0

-1,-1,5

1

-1,-2,7

2

Added: 5

extract_maxmax-heapswap [0↔1]

-1,-2,7

0

-1,-1,5

1

Added: 4

Key Takeaways

✓ Frequency and recency together determine the element returned by pop.

This is hard to see from code alone because it requires understanding the heap ordering by two keys simultaneously.

✓ The heap uses negative frequency and timestamp to simulate a max heap with Python's min heap.

This trick is subtle but crucial to maintain max priority behavior using standard heapq.

✓ Each pop updates frequency and may remove elements from the frequency map, affecting future heap ordering.

Seeing frequency decrements and removals visually clarifies how the data structures stay consistent.

Practice

1. You are given an unsorted array of integers and asked to find the k-th smallest absolute difference between any two elements. Which approach guarantees an optimal solution in terms of time complexity?

easy

A. Use a brute force nested loop to generate all pairs, then sort the distances and pick the k-th smallest.

B. Sort the array, then use a min-heap to merge pairs starting from adjacent elements to efficiently find the k-th smallest pair distance.

C. Use dynamic programming to build a table of pair distances and select the k-th smallest from the table.

D. Apply a greedy algorithm that repeatedly selects the smallest available pair distance without sorting.

Solution

1. Step 1: Understand problem constraints and approaches

   Brute force (A) is correct but inefficient with O(n^2 log n) time. Dynamic programming (C) is not applicable as pair distances don't form overlapping subproblems. Greedy (D) fails because pair distances are not independent and require sorting.

2. Step 2: Identify optimal approach

   Sorting the array and using a min-heap to merge pairs starting from adjacent elements (B) leverages sorted order to generate pairs in ascending order efficiently, achieving O(n log n + k log n) time complexity.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Heap-based merging of sorted pairs is optimal and efficient [OK]

Hint: Heap merge after sorting is optimal for k-th smallest pair distance [OK]

Common Mistakes:

• Assuming DP applies to pair distances
• Thinking greedy works without sorting
• Believing brute force is optimal

2. Consider the following Python code that finds the maximum CPU load from a list of jobs. What is the value of max_load after processing all events for the input jobs = [[1,4,3], [2,5,4], [7,9,6]]?

def find_max_cpu_load(jobs):
    events = []
    for start, end, load in jobs:
        events.append((start, load))
        events.append((end, -load))
    events.sort(key=lambda x: x[0])

    current_load = 0
    max_load = 0
    for _, load_change in events:
        current_load += load_change
        max_load = max(max_load, current_load)
    return max_load

jobs = [[1,4,3], [2,5,4], [7,9,6]]
print(find_max_cpu_load(jobs))

easy

A. 7

B. 6

C. 9

D. 4

Solution

1. Step 1: List all events sorted by time:

   Events: (1,+3), (2,+4), (4,-3), (5,-4), (7,+6), (9,-6)

2. Step 2: Trace current_load and max_load through events:

   At 1: current_load=3, max_load=3; at 2: current_load=7, max_load=7; at 4: current_load=4, max_load=7; at 5: current_load=0, max_load=7; at 7: current_load=6, max_load=7; at 9: current_load=0, max_load=7.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Maximum overlap load is 7 at time 2 [OK]

Hint: Sum loads at event times, track max load [OK]

Common Mistakes:

• Off-by-one in event processing
• Ignoring negative load at job end

3. Given the following Python code implementing the optimal bucket sort approach, what is the final returned string when the input is "abbccc"?

from collections import Counter

def frequencySort(s: str) -> str:
    freq = Counter(s)
    max_freq = max(freq.values(), default=0)
    buckets = [[] for _ in range(max_freq + 1)]
    for char, count in freq.items():
        buckets[count].append(char)
    result = []
    for freq_count in range(max_freq, 0, -1):
        for char in buckets[freq_count]:
            result.append(char * freq_count)
    return ''.join(result)

print(frequencySort("abbccc"))

easy

A. "ccc bba"

B. "ccc bba" is invalid; correct is "ccc bba" without spaces

C. "ccc bba" (with spaces between groups)

D. "cccbba"

Solution

1. Step 1: Count frequencies

   Characters: 'a':1, 'b':2, 'c':3; max_freq = 3.

2. Step 2: Fill buckets and build result

   buckets[3] = ['c'], buckets[2] = ['b'], buckets[1] = ['a']; concatenation: 'c'*3 + 'b'*2 + 'a'*1 = "cccbba" without spaces.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Output matches frequency descending order "cccbba" without spaces [OK]

Hint: Trace frequency buckets from max to min frequency [OK]

Common Mistakes:

• Appending spaces mistakenly
• Off-by-one in bucket indices

4. You are given an integer array and asked to find the k elements that appear most frequently. Which of the following approaches guarantees an optimal time complexity solution for this problem?

easy

A. Use a bucket sort based on frequency counts, then iterate buckets from high to low frequency to collect top k elements.

B. Use a greedy approach that picks the most frequent element repeatedly without frequency counting.

C. Use a dynamic programming approach to build frequency tables and select top k elements.

D. Sort the entire array and then count frequencies to pick top k elements.

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding the top k frequent elements efficiently, which means counting frequencies and retrieving elements by frequency.

2. Step 2: Evaluate approaches for optimality

   Sorting the entire array (A) is inefficient (O(n log n)). Dynamic programming (C) and greedy without frequency counting (B) do not apply here. Bucket sort by frequency (D) achieves O(n) time by grouping elements by frequency and iterating from highest frequency down.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Bucket sort groups elements by frequency and retrieves top k in linear time [OK]

Hint: Bucket sort by frequency is linear time [OK]

Common Mistakes:

• Sorting entire array instead of unique elements
• Using greedy without frequency counts

5. Consider the following buggy implementation of the KthLargest class. Which line contains the subtle bug that can cause incorrect kth largest results?

import heapq

class KthLargest:
    def __init__(self, k: int, nums: list[int]):
        self.k = k
        self.heap = nums
        heapq.heapify(self.heap)
        # Bug: missing while loop to reduce heap size

    def add(self, val: int) -> int:
        if len(self.heap) < self.k:
            heapq.heappush(self.heap, val)
        elif val > self.heap[0]:
            heapq.heapreplace(self.heap, val)
        return self.heap[0]

medium

A. Missing while loop after heapify to pop extra elements

B. Line 6: self.heap = nums

C. Line 7: heapq.heapify(self.heap)

D. Line 5: self.k = k

Solution

1. Step 1: Analyze initialization

   The constructor heapifies the input list but does not reduce its size to k, so heap may contain more than k elements.

2. Step 2: Identify impact of missing size reduction

   Without popping extra elements, the heap size can exceed k, causing add() to behave incorrectly and return wrong kth largest values.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing size trimming after heapify breaks heap size invariant [OK]

Hint: Heap size must be trimmed to k after heapify [OK]

Common Mistakes:

• Forgetting to pop extra elements after heapify
• Misusing heapreplace when heap size < k
• Incorrectly initializing heap with nums reference