Welcome to Day 7 of your coding interview journey.

You’ve already built a strong foundation:

• ✅ Day 1: HashMaps
• ✅ Day 2: Sliding Window
• ✅ Day 3: Arrays
• ✅ Day 4: Two Pointers
• ✅ Day 5: Interval Problems
• ✅ Day 6: Binary Search

Today, we move into a very powerful and slightly more advanced topic:

👉 Heaps (Priority Queues)

---

🧠 What is a Heap?

A Heap is a special tree-based data structure that allows you to efficiently get:

• The smallest element (Min Heap)
• The largest element (Max Heap)

In Python, we use:

import heapq

👉 By default, Python implements a Min Heap

---

🔑 When Should You Use a Heap?

Look for these patterns:

• “Top K” elements
• Kth largest/smallest
• Streaming data
• Priority-based processing

---

💡 Problem 1 – Top K Frequent Elements

---

🧩 Problem

Given an array nums, return the k most frequent elements.

---

✅ Example

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

Output:

[1,2]

---

🧠 Approach – HashMap + Heap

Steps:

1. Count frequencies using a HashMap
2. Use a heap to get top K elements

---

🛠️ Solution in Python

import heapq
from collections import Counter

def top_k_frequent(nums, k):
    count = Counter(nums)

    # Min heap
    heap = []

    for num, freq in count.items():
        heapq.heappush(heap, (freq, num))

        if len(heap) > k:
            heapq.heappop(heap)

    return [num for freq, num in heap]

---

⚡ Complexity

• Time: O(n log k)
• Space: O(n)

---

🎯 Key Insight

👉 Keep the heap size at k

This avoids sorting the entire array (O(n log n)).

---

💡 Problem 2 – Kth Largest Element in an Array

---

🧩 Problem

Given an array nums, return the kth largest element.

---

✅ Example

nums = [3,2,1,5,6,4]
k = 2

Output:

5

---

🧠 Approach – Min Heap of Size K

We maintain a heap of the k largest elements.

---

🛠️ Solution in Python

import heapq

def find_kth_largest(nums, k):
    heap = []

    for num in nums:
        heapq.heappush(heap, num)

        if len(heap) > k:
            heapq.heappop(heap)

    return heap[0]

---

⚡ Complexity

• Time: O(n log k)
• Space: O(k)

---

🔥 Alternative (Quickselect – Advanced)

👉 You can solve this in O(n) average time using Quickselect

But heaps are usually simpler and safer in interviews.

---

⚠️ Common Mistakes

• ❌ Using full sorting instead of heap
• ❌ Forgetting heap size constraint
• ❌ Confusing min heap vs max heap
• ❌ Not understanding tuple ordering (freq, num)

---

🧪 Practice Problems

To master heaps, try:

1. Merge K sorted lists
2. Find median from data stream
3. K closest points to origin
4. Task scheduler
5. Reorganize string

---

🎯 Key Takeaways

• Heaps are perfect for:
  • Top K problems
  • Priority-based tasks
• Optimize from:
  • O(n log n) → O(n log k)
• Python tip:
  • Use heapq (Min Heap by default)

---

🚀 Your Challenge (Day 7)

Solve this:

Find the K closest numbers to a target in an array.

---

📌 Final Thoughts

Heaps are a game-changer for interview problems involving ranking and frequency.

You don’t need to master trees deeply — just understand how to use heaps effectively.