281. Kth Largest Element in a Stream

🔗 LeetCode Problem: 703. Kth Largest Element in a Stream
📊 Difficulty: Easy
🏷️ Topics: Tree, Design, Binary Search Tree, Heap (Priority Queue), Binary Tree, Data Stream

Problem Statement

Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Implement KthLargest class:

• KthLargest(int k, int[] nums) Initializes the object with the integer k and the stream of integers nums.
• int add(int val) Appends the integer val to the stream and returns the element representing the kth largest element in the stream.

Example 1:

Input:
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]

Output:
[null, 4, 5, 5, 8, 8]

Explanation:
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3);   // return 4
kthLargest.add(5);   // return 5
kthLargest.add(10);  // return 5
kthLargest.add(9);   // return 8
kthLargest.add(4);   // return 8

Constraints: - 1 <= k <= 10^4 - 0 <= nums.length <= 10^4 - -10^4 <= nums[i] <= 10^4 - -10^4 <= val <= 10^4 - At most 10^4 calls will be made to add - It is guaranteed that there will be at least k elements in the array when you search for the kth element

---

🌟 Understanding the Problem

What is "kth largest"?

Array: [4, 5, 8, 2], k = 3

Sorted (descending): [8, 5, 4, 2]
                      ↑  ↑  ↑
                     1st 2nd 3rd largest

3rd largest = 4

After adding 3: [4, 5, 8, 2, 3]
Sorted: [8, 5, 4, 3, 2]
         ↑  ↑  ↑
        1st 2nd 3rd largest

3rd largest = 4 (still!)

After adding 10: [4, 5, 8, 2, 3, 10]
Sorted: [10, 8, 5, 4, 3, 2]
         ↑   ↑  ↑
        1st 2nd 3rd largest

3rd largest = 5 (changed!)

Key Observations:

1. Stream of numbers (keeps growing)
   → Can't use fixed-size array

2. Need kth largest after EACH addition
   → Must be efficient per add operation

3. k is fixed
   → Only care about top k elements
   → Elements smaller than kth largest don't matter!

4. Numbers can be duplicates
   → [5, 5, 5] with k=2 → answer is 5

---

🌟 The Natural Thinking Process

When you first see this problem:

Question: Find kth largest after each addition

First Thought: "Sort array after each add, return kth element"
  - Add new element
  - Sort entire array
  - Return nums[k-1] (kth largest)

Is this optimal? NO (sort every time!), but it WORKS!
Let's try it to understand.

The Evolution:

BRUTE FORCE THINKING:
  "Add element → Sort all → Return kth"
  Time per add: O(n log n) for sorting
  Problem: Re-sorting entire array is wasteful!
  ⬇

REALIZATION 1:
  "Array is already sorted before adding!"
  "Can insert in sorted position!"
  ⬇

OPTIMIZATION 1: Maintain Sorted List
  "Binary search to find insert position"
  "Insert element, return kth"
  Time per add: O(n) for insertion
  Better but still O(n)...
  ⬇

REALIZATION 2:
  "I only care about TOP K elements!"
  "Elements beyond kth largest don't matter!"
  "Similar to Problem 275 (Kth Largest Element)!"
  ⬇

OPTIMIZATION 2: Min-Heap of Size K
  "Keep heap of only k largest elements"
  "Min on top = kth largest!"
  Time per add: O(log k) - OPTIMAL! ✨

---

🎯 Approach 1: Brute Force - Sort on Each Add ⭐

The First Natural Solution

The Thought Process:

Step 1: Store all elements in a list

Step 2: When adding:
  - Add to list
  - Sort list
  - Return kth largest (index k-1 from end)

Simple but inefficient!

Visual Tracking - Complete Example

k = 3, initial = [4, 5, 8, 2]

═══════════════════════════════════════════════════════════════
INITIALIZATION
═══════════════════════════════════════════════════════════════

List: [4, 5, 8, 2]

═══════════════════════════════════════════════════════════════
ADD(3)
═══════════════════════════════════════════════════════════════

Step 1: Add 3 to list
  List: [4, 5, 8, 2, 3]

Step 2: Sort list (descending)
  Sorted: [8, 5, 4, 3, 2]

Step 3: Return kth largest (k=3)
  Index: k-1 = 2
  Element: sorted[2] = 4

Return: 4 ✓

═══════════════════════════════════════════════════════════════
ADD(5)
═══════════════════════════════════════════════════════════════

Step 1: Add 5 to list
  List: [4, 5, 8, 2, 3, 5]

Step 2: Sort (descending)
  Sorted: [8, 5, 5, 4, 3, 2]

Step 3: Return kth largest
  sorted[2] = 5

Return: 5 ✓

═══════════════════════════════════════════════════════════════
ADD(10)
═══════════════════════════════════════════════════════════════

Step 1: Add 10
  List: [4, 5, 8, 2, 3, 5, 10]

Step 2: Sort
  Sorted: [10, 8, 5, 5, 4, 3, 2]

Step 3: Return kth largest
  sorted[2] = 5

Return: 5 ✓

═══════════════════════════════════════════════════════════════

Implementation

import java.util.*;

/**
 * Brute Force: Sort on each add
 * Time per add: O(n log n)
 * Space: O(n)
 */
class KthLargest {
    private List<Integer> nums;
    private int k;

    public KthLargest(int k, int[] nums) {
        this.k = k;
        this.nums = new ArrayList<>();
        for (int num : nums) {
            this.nums.add(num);
        }
    }

    public int add(int val) {
        // Add new element
        nums.add(val);

        // Sort in descending order
        Collections.sort(nums, Collections.reverseOrder());

        // Return kth largest
        return nums.get(k - 1);
    }
}

⏰ Time per add: O(n log n) - Sorting entire list
💾 Space: O(n) - Store all elements

Why This is Inefficient:

Problem: Sorts ENTIRE list on every add!

Example: 10,000 elements
  add() called 10,000 times
  Each add: O(10,000 log 10,000)
  Total: O(100,000,000) operations! 😱

Most elements don't even matter!
  If k = 3, only top 3 matter
  Sorting all 10,000 is wasteful!

---

💡 The First AHA Moment

OBSERVATION:

Before add: [8, 5, 4, 3, 2] (sorted)
Add 5: [8, 5, 4, 3, 2, 5] (unsorted)
Sort: [8, 5, 5, 4, 3, 2] (sorted again)

We're re-sorting an already sorted list!

INSIGHT:
  "List is sorted before adding"
  "Can use binary search to find insert position"
  "Insert in sorted position → stays sorted!"

  No need to sort entire list!
  Just maintain sorted order!

---

🎯 Approach 2: Maintain Sorted List ⭐⭐

Better Solution with Binary Search

The Evolution of Thought:

Brute Force: Sort every time
  ⬇
Observation: "List already sorted!"
  ⬇
Better Idea: "Insert in sorted position!"

Visual Tracking

k = 3, initial = [4, 5, 8, 2]

═══════════════════════════════════════════════════════════════
INITIALIZATION
═══════════════════════════════════════════════════════════════

Sort initial array:
  List: [8, 5, 4, 2] (descending)

═══════════════════════════════════════════════════════════════
ADD(3)
═══════════════════════════════════════════════════════════════

Current sorted list: [8, 5, 4, 2]

Binary search to find insert position for 3:
  3 goes between 4 and 2
  Position: index 3

Insert at position 3:
  List: [8, 5, 4, 3, 2]

Return kth largest:
  list[2] = 4

═══════════════════════════════════════════════════════════════
ADD(5)
═══════════════════════════════════════════════════════════════

Current: [8, 5, 4, 3, 2]

Binary search for 5:
  5 equals list[1]
  Insert at index 2 (after existing 5)

List: [8, 5, 5, 4, 3, 2]

Return: list[2] = 5

Implementation

import java.util.*;

/**
 * Maintain sorted list with binary search
 * Time per add: O(n) for insertion
 * Space: O(n)
 */
class KthLargest {
    private List<Integer> nums;
    private int k;

    public KthLargest(int k, int[] nums) {
        this.k = k;
        this.nums = new ArrayList<>();
        for (int num : nums) {
            this.nums.add(num);
        }
        // Sort once at initialization
        Collections.sort(this.nums, Collections.reverseOrder());
    }

    public int add(int val) {
        // Binary search to find insert position
        int pos = binarySearch(val);

        // Insert at position
        nums.add(pos, val);

        // Return kth largest
        return nums.get(k - 1);
    }

    private int binarySearch(int val) {
        int left = 0, right = nums.size();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums.get(mid) > val) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

⏰ Time per add: O(n) - Binary search O(log n) + insertion O(n)
💾 Space: O(n)

Why Still Not Optimal:

Better than O(n log n), but still O(n) per add!

Problem: ArrayList insertion is O(n)
  Must shift all elements after insert position

Example: Insert at position 0 in list of 10,000
  Must shift 10,000 elements!

Also: We're storing ALL elements
  But only top k matter!

---

💡 The Second AHA Moment - The Critical Insight

OBSERVATION:

k = 3
Array: [10, 8, 5, 4, 3, 2, 1]
        ↑   ↑  ↑  ↑  ↑  ↑  ↑
       1st 2nd 3rd
                   └─ These don't matter!

Only top 3 elements affect the answer!
Elements 4, 3, 2, 1 are irrelevant!

KEY INSIGHT:
  "Only track TOP K elements!"
  "Smallest of top k = kth largest!"

  This is EXACTLY like Problem 275 (Kth Largest Element)!
  And Problem 278 (Top K Frequent)!

  Use MIN-HEAP of size k! ✨

---

🎯 Approach 3: Min-Heap of Size K (Optimal) ⭐⭐⭐

The Optimal Solution

The Evolution of Thought:

Brute Force: Sort all
  ⬇
Better: Maintain sorted list
  ⬇
Observation: "Only top k matter!"
  ⬇
Optimal: "Min-heap of size k!"

Understanding Min-Heap of Size K - Complete Explanation

Why Min-Heap of Size K works?

THE BRILLIANT STRATEGY:

Goal: Track kth largest element

Strategy:
  - Keep heap of ONLY k largest elements
  - Heap size = k (fixed!)
  - Min-heap: smallest of k largest on top
  - Top element = kth largest! ✨

Why min-heap not max-heap?
  Min-heap: Top = smallest of top k = kth largest
  Max-heap: Top = largest = 1st largest (wrong!)

Example: k = 3, elements = [10, 8, 5, 4, 2]

Keep top 3: [10, 8, 5]
Min-heap: [5, 8, 10]
           ↑
          min (3rd largest) ✓

WHY Min-Heap of Size K Works - Critical Reasoning

The Core Question:

Why does keeping k elements in min-heap give kth largest?
Why is min (top) of heap the answer?
Why do we evict smallest when adding?

Answer Through Detailed Reasoning:

PRINCIPLE 1: Definition of Kth Largest
═══════════════════════════════════════════════════════════════

"Kth largest" means:
  - k-1 elements are larger
  - All remaining elements are smaller or equal

Example: [10, 8, 5, 4, 2], k = 3
  3rd largest = 5

  2 elements larger: 10, 8 ✓
  2 elements smaller: 4, 2 ✓

  5 is the "boundary" element!

═══════════════════════════════════════════════════════════════
PRINCIPLE 2: Heap Contains Top K
═══════════════════════════════════════════════════════════════

If heap has exactly k largest elements:
  - Largest k elements in heap
  - All other elements smaller

The SMALLEST element in heap = kth largest!

Why?
  - k elements in heap
  - Smallest of these k = kth overall
  - By definition! ✓

Example: All elements = [10, 8, 5, 4, 2], k = 3
  Heap = [10, 8, 5] (top 3)
  Min of heap = 5 = 3rd largest ✓

═══════════════════════════════════════════════════════════════
PRINCIPLE 3: Min-Heap Gives Smallest
═══════════════════════════════════════════════════════════════

Min-heap property:
  Top element = minimum of all in heap

If heap has k largest elements:
  Top = min of k largest = kth largest ✓

Example: Heap = [5, 8, 10]
  Min-heap structure:
    5
   / \
  8   10

  Top = 5 (peek) = 3rd largest ✓
  Instant access in O(1)!

═══════════════════════════════════════════════════════════════
PRINCIPLE 4: When to Add/Remove
═══════════════════════════════════════════════════════════════

When adding new element:

CASE 1: Heap not full (size < k)
  - Add to heap unconditionally
  - Heap growing to size k

CASE 2: Heap full, new element > min
  - New element is larger than kth largest!
  - Remove min (current kth)
  - Add new element
  - Heap still has k largest!

CASE 3: Heap full, new element ≤ min
  - New element not in top k
  - Don't add (would kick out larger element)
  - Min stays same

Example visualizations:

Heap = [5, 8, 10], k = 3

Add 12:
  12 > 5 (min)? YES
  Remove 5, add 12
  Heap = [8, 10, 12]
  New 3rd largest = 8 ✓

Add 3:
  3 > 5 (min)? NO
  Don't add (3 not in top 3)
  Heap = [5, 8, 10]
  3rd largest still 5 ✓

═══════════════════════════════════════════════════════════════
WHY Evict Smallest When Full?
═══════════════════════════════════════════════════════════════

Question: Why remove min when heap full and adding larger?

Reasoning:
  Heap has k largest elements currently
  New element is larger than min (kth largest)
  → New element should be in top k!

  But heap can only hold k elements
  → Must remove one element

  Which to remove?
  → Remove smallest (min/top)!

  Why?
    - Min is current kth largest
    - New element is larger
    - New element becomes new member of top k
    - Old kth largest kicked out
    - New kth largest = next smallest in heap ✓

Visual:
  Before: Heap = [5, 8, 10]  (top 3)
          Other elements: [4, 2, 1]

  Add 12:
    12 is larger than 5
    12 should be in top 3!
    New top 3: [8, 10, 12]
    5 no longer in top 3

  After: Heap = [8, 10, 12]
         Other elements: [4, 2, 1, 5]

  New 3rd largest = 8 ✓

═══════════════════════════════════════════════════════════════
SUMMARY: The Complete Logic
═══════════════════════════════════════════════════════════════

1. GOAL: Find kth largest
   → Need to track top k elements

2. HEAP SIZE: Keep exactly k elements
   → Smallest of these k = kth largest

3. MIN-HEAP: Top = minimum of k
   → Top = kth largest (O(1) access)

4. ADD LOGIC:
   If size < k: Add unconditionally
   If size = k and val > top: Remove top, add val
   If size = k and val ≤ top: Skip (not in top k)

5. EFFICIENCY:
   Heap operations: O(log k)
   Only k elements stored: Space O(k)
   Much better than O(n)! ✨

This is the MAGIC of min-heap of size k! 🎯

Visual Tracking - Complete Example

k = 3, initial = [4, 5, 8, 2]

═══════════════════════════════════════════════════════════════
INITIALIZATION: Build Heap
═══════════════════════════════════════════════════════════════

Add elements to heap maintaining size ≤ k:

Add 4: heap = [4]
  Size 1 < k, add directly

Add 5: heap = [4, 5]
  Size 2 < k, add directly
  Min-heap adjusts: [4, 5]

Add 8: heap = [4, 5, 8]
  Size 3 = k, heap full!
  Heap structure:
    4
   / \
  5   8

Add 2: heap = [4, 5, 8]
  Size = k and 2 < 4 (top)
  2 not in top 3, skip!
  Heap unchanged

Initial heap: [4, 5, 8]
Top = 4 = 3rd largest ✓

═══════════════════════════════════════════════════════════════
ADD(3)
═══════════════════════════════════════════════════════════════

Heap: [4, 5, 8], size = 3 = k

New element: 3
Compare: 3 vs 4 (top)
  3 < 4? YES
  3 not in top 3, skip!

Heap: [4, 5, 8] (unchanged)
Return: top = 4 ✓

Current elements: [4, 5, 8, 2, 3]
Top 3: [8, 5, 4]
3rd largest: 4 ✓

═══════════════════════════════════════════════════════════════
ADD(5)
═══════════════════════════════════════════════════════════════

Heap: [4, 5, 8], size = 3

New element: 5
Compare: 5 vs 4 (top)
  5 > 4? YES
  5 should be in top 3!

Remove top: poll() → 4 removed
Heap: [5, 8]

Add 5: offer(5)
Heap: [5, 5, 8]
  Structure:
    5
   / \
  5   8

Return: top = 5 ✓

Current elements: [4, 5, 8, 2, 3, 5]
Top 3: [8, 5, 5]
3rd largest: 5 ✓

═══════════════════════════════════════════════════════════════
ADD(10)
═══════════════════════════════════════════════════════════════

Heap: [5, 5, 8]

New element: 10
Compare: 10 vs 5 (top)
  10 > 5? YES
  10 in top 3!

Remove top: 5 removed
Heap: [5, 8]

Add 10: 
Heap: [5, 8, 10]
  Structure:
    5
   / \
  8   10

Return: top = 5 ✓

Current elements: [4, 5, 8, 2, 3, 5, 10]
Top 3: [10, 8, 5]
3rd largest: 5 ✓

═══════════════════════════════════════════════════════════════
ADD(9)
═══════════════════════════════════════════════════════════════

Heap: [5, 8, 10]

New element: 9
Compare: 9 vs 5 (top)
  9 > 5? YES
  9 in top 3!

Remove top: 5 removed
Heap: [8, 10]

Add 9:
Heap: [8, 9, 10]
  Structure:
    8
   / \
  9   10

Return: top = 8 ✓

Current elements: [4, 5, 8, 2, 3, 5, 10, 9]
Top 3: [10, 9, 8]
3rd largest: 8 ✓

═══════════════════════════════════════════════════════════════
ADD(4)
═══════════════════════════════════════════════════════════════

Heap: [8, 9, 10]

New element: 4
Compare: 4 vs 8 (top)
  4 < 8? YES
  4 not in top 3, skip!

Heap: [8, 9, 10] (unchanged)
Return: top = 8 ✓

Current elements: [4, 5, 8, 2, 3, 5, 10, 9, 4]
Top 3: [10, 9, 8]
3rd largest: 8 ✓

═══════════════════════════════════════════════════════════════
SUMMARY
═══════════════════════════════════════════════════════════════

Sequence of answers: [4, 5, 5, 8, 8]

Key observations:
  ✓ Heap always size ≤ k
  ✓ Top always = kth largest
  ✓ Only track top k elements
  ✓ Efficient O(log k) per add

Implementation

import java.util.*;

/**
 * Min-Heap of size k (Optimal)
 * Time per add: O(log k)
 * Space: O(k)
 */
class KthLargest {
    private PriorityQueue<Integer> minHeap;
    private int k;

    public KthLargest(int k, int[] nums) {
        this.k = k;
        this.minHeap = new PriorityQueue<>();  // Min-heap by default

        // Initialize heap with all elements
        for (int num : nums) {
            add(num);
        }
    }

    public int add(int val) {
        // If heap not full, add unconditionally
        if (minHeap.size() < k) {
            minHeap.offer(val);
        }
        // If heap full and new element larger than min
        else if (val > minHeap.peek()) {
            minHeap.poll();    // Remove smallest of top k
            minHeap.offer(val); // Add new element
        }
        // Else: val ≤ min, not in top k, skip

        // Top of min-heap = kth largest
        return minHeap.peek();
    }
}

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest obj = new KthLargest(k, nums);
 * int param_1 = obj.add(val);
 */

⏰ Time per add: O(log k) - Heap operations
💾 Space: O(k) - Store only k elements

Why This is Optimal:

✓ O(log k) per add vs O(n log n) brute force
✓ O(k) space vs O(n) space
✓ Only tracks relevant elements (top k)
✓ Instant access to kth largest (peek)

Example improvement:
  n = 10,000, k = 100

  Brute force per add:
    Sort 10,000: O(10,000 log 10,000) ≈ 130,000 ops

  Optimal per add:
    Heap ops: O(log 100) ≈ 7 ops

  18,000x FASTER! 🚀

Perfect! Can't do better than O(log k)!

---

📊 Approach Comparison - The Complete Growth Journey

┌───────────────┬──────────────┬──────────┬─────────────────────┐
│ Approach      │ Time per add │ Space    │ Key Insight         │
├───────────────┼──────────────┼──────────┼─────────────────────┤
│ Sort each add │ O(n log n)   │ O(n)     │ Simple but wasteful │
│ Sorted list   │ O(n)         │ O(n)     │ Maintain order      │
│ Min-heap k    │ O(log k)     │ O(k)     │ Only track top k    │
└───────────────┴──────────────┴──────────┴─────────────────────┘

THE COMPLETE LEARNING PROGRESSION:

Level 1: Brute Force
  Thought: "Sort after each add"
  Works? YES ✓
  Optimal? NO ✗
  Time: O(n log n) per add
  Problem: Re-sorts everything

Level 2: Observation #1
  Insight: "List already sorted!"
  Idea: "Insert in sorted position"

Level 3: Better Solution
  Implementation: Binary search + insert
  Result: O(n) per add
  Better: No full sort ✓
  But: Still O(n) for insertion

Level 4: Observation #2
  Insight: "Only top k matter!"
  Pattern: "Same as Problem 275, 278!"
  Idea: "Min-heap of size k!"

Level 5: Optimal Solution
  Implementation: Min-heap
  Result: O(log k) per add ✓
  Perfect: Only k elements tracked! ✨
  Growth: Learned streaming data pattern!

CONCRETE EXAMPLE (n=10,000, k=100):

Sort each add:
  10,000 × log(10,000) ≈ 130,000 ops per add
  10,000 adds: 1.3 billion ops! 😱

Min-heap:
  log(100) ≈ 7 ops per add
  10,000 adds: 70,000 ops

  18,000x improvement! 🚀
  Space: 100 elements vs 10,000!
  100x less memory! ✨

---

💡 Key Learnings - Your Complete Growth

WHAT YOU LEARNED:

1. STREAMING DATA PATTERN:
   ✓ Elements arrive one at a time
   ✓ Need result after EACH addition
   ✓ Can't wait to process all at once
   ✓ Must be efficient per operation

2. WHY MIN-HEAP OF SIZE K:
   ✓ Only top k elements matter
   ✓ Min of top k = kth largest
   ✓ Min-heap gives min in O(1)
   ✓ Maintain size k with O(log k) ops

3. WHY MIN NOT MAX:
   ✓ Max-heap: top = 1st largest (wrong!)
   ✓ Min-heap: top = smallest of top k = kth largest (correct!)
   ✓ Size matters for complexity!

4. WHEN TO ADD/REMOVE:
   ✓ Size < k: Always add
   ✓ Size = k, val > min: Replace min
   ✓ Size = k, val ≤ min: Skip
   ✓ Logic ensures top k maintained

5. PATTERN RECOGNITION:
   ✓ Same as Problem 275 (Kth Largest)
   ✓ Same as Problem 278 (Top K Frequent)
   ✓ "Top k" → Think min-heap of size k!

INTERVIEW STRATEGY:

Progressive Presentation:
  "I see three approaches:

   Approach 1: Sort after each add
   - Simple but O(n log n) per add
   - Wasteful re-sorting

   Approach 2: Maintain sorted list
   - Binary search to insert: O(log n)
   - But insertion still O(n)
   - Better but not optimal

   Approach 3: Min-heap of size k
   - Key insight: Only top k matter!
   - Min-heap of k elements
   - Top = smallest of top k = kth largest
   - O(log k) per add

   Let me explain why min-heap works:
   [explain top k concept]
   [explain why min not max]
   [explain when to add/remove]

   Time: O(log k), Space: O(k)

   This is optimal!"

Shows:
  ✓ Understanding of all approaches
  ✓ Pattern recognition (streaming)
  ✓ Min-heap of size k reasoning
  ✓ Complete justification
  ✓ Optimal solution

This is REAL mastery! 🌱→🌳→🏆

---

⚠️ Common Mistakes

Mistake 1: Using max-heap

// ❌ WRONG - Max-heap top = 1st largest, not kth!
PriorityQueue<Integer> maxHeap = 
    new PriorityQueue<>(Collections.reverseOrder());

// ✓ CORRECT - Min-heap top = kth largest
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

Mistake 2: Not checking heap size

// ❌ WRONG - Always removes even when size < k
if (val > minHeap.peek()) {
    minHeap.poll();
    minHeap.offer(val);
}

// ✓ CORRECT - Check size first
if (minHeap.size() < k) {
    minHeap.offer(val);
} else if (val > minHeap.peek()) {
    minHeap.poll();
    minHeap.offer(val);
}

Mistake 3: Adding all initial elements unconditionally

// ❌ WRONG - Might store more than k elements
for (int num : nums) {
    minHeap.offer(num);
}

// ✓ CORRECT - Use add logic for all
for (int num : nums) {
    add(num);  // Maintains size ≤ k
}

Mistake 4: Wrong comparison

// ❌ WRONG - Should compare with top (min)
if (val > k) {  // Comparing with k value!
    // ...
}

// ✓ CORRECT - Compare with heap top
if (val > minHeap.peek()) {
    // ...
}

---

🎯 Pattern Recognition

Problem Type: Streaming Data with Top K
Core Pattern: Min-Heap of Size K

When to Apply:
✓ Elements arrive one at a time (stream)
✓ Need top k elements continuously
✓ Need kth largest/smallest repeatedly
✓ Can't wait to process all data

Recognition Keywords:
- "stream"
- "kth largest/smallest"
- "continuously"
- "after each addition"

Similar Problems:
- Kth Largest Element (LC 215) - Static array version
- Top K Frequent Elements (LC 347) - By frequency
- Find Median from Data Stream (LC 295) - Two heaps
- Sliding Window Median (LC 480) - Moving window

Key Components:
┌────────────────────────────────────────────┐
│ Min-Heap: Size k for kth largest          │
│ Max-Heap: Size k for kth smallest         │
│ Top: Always gives kth element             │
│ Add: O(log k) per operation               │
│ Space: O(k) not O(n)                      │
└────────────────────────────────────────────┘

---

📝 Quick Revision Notes

🎯 Core Concept:

Find kth largest in stream. Brute force: Sort each add O(n log n). Better: Maintain sorted O(n) insert. Optimal: Min-heap of size k O(log k). Keep only top k elements, min on top = kth largest. Add if val > top or size < k. O(log k) per add!

⚡ Quick Implementation:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

class KthLargestSorting {
  List<Integer> nums;
  int k;

  public KthLargestSorting(int k, int[] a) {
    // step 1: initialize
    this.nums = new ArrayList<>();
    for (int num : a) {
      this.nums.add(num);
    }

    this.k = k;

    // step 2: sort the list and keep it ready
    Collections.sort(this.nums);
  }

  public int add(int val) {
    // step 3: Get position of index at which val to
    // be inserted (normal binary search)
    int index = binarySearch(val);

    // step 4: add val at that index
    this.nums.add(index, val);

    // step 5: get kth largest
    return this.nums.get(this.nums.size() - this.k);
  }

  private int binarySearch(int val) {
    int left = 0;
    int right = this.nums.size() - 1;

    while (left <= right) {
      int mid = right + (left - right) / 2;
      int midElement = this.nums.get(mid);

      if (midElement == val) {
        return mid;
      } else if (midElement < val) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }

    return left;
  }
}

class KthLargest {
  PriorityQueue<Integer> pq;
  int k;

  public KthLargest(int k, int[] a) {
    // step 1: initialize (minheap - provides min
    // element on heap always)
    this.pq = new PriorityQueue<>();
    this.k = k;

    for (int num : a) {
      // step 2: Always maintain heap size of k larger elements.
      if (this.pq.size() < this.k) {
        // if its less, simply add it.
        this.pq.offer(num);
      } else {
        // if it becomes greater, now we have to decide, if
        // we need to take incoming elements or not
        if (this.pq.peek() < num) {
          this.pq.poll();
          this.pq.offer(num);
        }
      }
    }
  }

  public int add(int val) {
    // step 3: exactly same as above.
    // for simple understanding, I did copy paste.
    // to make it standard, directly call this logic from above.
    if (this.pq.size() < this.k) {
      this.pq.offer(val);
    } else {
      if (this.pq.peek() < val) {
        this.pq.poll();
        this.pq.offer(val);
      }
    }

    return this.pq.peek();
  }
}

public class Solution {
  public static void main(String[] args) {
    KthLargest k1 = new KthLargest(3, new int[] { 4, 5, 8, 2 });
    System.out.println(k1.add(3) == 4);
    System.out.println(k1.add(5) == 5);
    System.out.println(k1.add(10) == 5);
    System.out.println(k1.add(9) == 8);
    System.out.println(k1.add(4) == 8);

    KthLargest k2 = new KthLargest(4, new int[] { 7, 7, 7, 7, 8, 3 });
    System.out.println(k2.add(2) == 7);
    System.out.println(k2.add(10) == 7);
    System.out.println(k2.add(9) == 7);
    System.out.println(k2.add(9) == 8);
  }
}

🔑 Key Insights:

• Why Min-Heap?: Top = smallest of top k = kth largest ✓
• Why Not Max?: Max-heap top = 1st largest (wrong!) ✗
• Size K: Only track top k, rest don't matter
• When Add: Size < k OR val > top
• When Skip: Size = k AND val ≤ top
• Peek: O(1) access to kth largest
• Per Add: O(log k) vs O(n log n) - HUGE! ✓

🎪 Memory Aid:

"Top K? Min-heap of K!"
"Min on top = Kth largest!"
"Size K, not N - that's the key!" ✨

---

🧪 Edge Cases

Case 1: k = 1 (largest element)

Heap size 1
Top always = largest element

Case 2: k = n (smallest element)

Heap has all elements
Top = smallest = nth largest

Case 3: Duplicates

nums = [5, 5, 5], k = 2
Heap = [5, 5]
2nd largest = 5 ✓

Case 4: Initial array smaller than k

k = 5, nums = [1, 2]
Heap = [1, 2]
Add 3, 4, 5 to reach size 5

All handled correctly! ✓

---

🎓 Complexity Analysis

Approach 1: Sort Each Add

Time per add: O(n log n)
  Sort entire list

Total for m adds: O(m × n log n)

Space: O(n)
  Store all elements

Approach 2: Sorted List

Time per add: O(n)
  Binary search: O(log n)
  Insert: O(n) shifting

Total for m adds: O(m × n)

Space: O(n)

Approach 3: Min-Heap of K

Time per add: O(log k)
  Heap operations only

Total for m adds: O(m × log k)

Space: O(k)
  Only k elements

Optimal! Much better when k << n!

---

Happy practicing! 🎯

Note: This problem is PERFECT for learning the "min-heap of size k for kth largest" pattern! You naturally start with sorting (simple but slow), realize you can maintain sorted order (better), then discover you only need top k elements (optimal). The key insight: only top k matter, min of top k = kth largest, use min-heap! Understanding WHY min not max (size matters!), WHY we evict smallest (maintain top k), and WHEN to add/skip (comparison logic) builds deep intuition. This pattern appears in MANY streaming/top-k problems! The jump from O(n log n) to O(log k) is MASSIVE when k << n! True pattern mastery! 💪✨🏆