InterviewQuestions

Chapter 7: Heap + Top K + Monotonic Stack

1. Heap

Use Case:
Find the largest or smallest number among N elements.

  • Push / Pop: O(log N)
  • Peek: O(1)

Common Problems:

  • Top K Problem:
    • Find Kth largest → use Min Heap
    • Find Kth smallest → use Max Heap

Example Problems:

    1. Merge k Sorted Lists
    1. Find Median from Data Stream
    1. Kth Smallest Element in a Sorted Matrix
    1. Find K Pairs with Smallest Sums
    1. Reorganize String

Top K Examples:

    1. Kth Largest Element in an Array
    1. Top K Frequent Words

2. Monotonic Stack

Concept:
Find the first smaller/larger element in O(N) time.

  • Monotonic Increasing Stack: find the first smaller value for each element.
  • Monotonic Decreasing Stack: find the first larger value for each element.

Example Problems:

    1. Next Greater Element I
    1. Next Greater Element II
    1. Daily Temperatures

3. Python Templates

Heap (Top K Frequent Words):

1
2
3
4
5
6
7
8
9
maps = {}
for w in words:
    maps[w] = maps.get(w, 0) + 1

heap = []
for word, count in maps.items():
    heapq.heappush(heap, Item(count, word))
    if len(heap) > k:
        heapq.heappop(heap)

Monotonic Stack:

1
2
3
4
5
6
7
stack = []
maps = {}
for idx, num in enumerate(nums):
    while stack and num > nums[stack[-1]]:
        key = stack.pop()
        maps[key] = idx
    stack.append(idx)

4. Java Templates

Heap (Top K Frequent Words):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
PriorityQueue<Item> pq = new PriorityQueue<>((x1, x2) -> {
    if (x1.freq == x2.freq) {
        return x2.word.compareTo(x1.word);
    }
    return Integer.compare(x1.freq, x2.freq);
});

Map<String, Integer> freq = new HashMap<>();
for (String word : words) {
    freq.put(word, freq.getOrDefault(word, 0) + 1);
}

for (Map.Entry<String, Integer> e : freq.entrySet()) {
    pq.add(new Item(e.getValue(), e.getKey()));
    if (pq.size() > k) pq.poll();
}

Monotonic Stack:

1
2
3
4
5
6
7
8
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < nums2.length; i++) {
    while (!stack.isEmpty() && nums2[stack.peek()] < nums2[i]) {
        int key = stack.pop();
        maps.put(key, i);
    }
    stack.push(i);
}