What happens if you sorting entire stream on every add?

Time limit exceeded on large inputs Fix: Use a min-heap of size k to maintain kth largest efficiently

What happens if you using max-heap instead of min-heap for kth largest?

Incorrect kth largest element returned Fix: Use min-heap to keep track of k largest elements, root is kth largest

What happens if you not handling initial nums properly?

Heap size may exceed k or initial elements ignored Fix: Add initial nums elements using add() logic or heapify and pop excess

What happens if you returning wrong index in sorted list approaches?

Off-by-one errors cause wrong kth largest Fix: Return element at index len(nums) - k when sorted ascending

Interview Preptop-k-elementseasyAmazonGoogleFacebook

Kth Largest in a Stream (Online)

Choose your preparation mode4 modes available

Try It Solution Trace

🎯

easyHEAPAmazonGoogleFacebook

Imagine you are monitoring live stock prices and want to continuously know the 3rd highest price at any moment as new prices stream in.

💡 This problem involves maintaining a dynamic data structure that updates as new elements arrive. Beginners often struggle because they try to sort the entire stream repeatedly, which is inefficient. Understanding how to maintain only the necessary elements efficiently is key.

📋

Problem Statement

Design a class that finds the kth largest element in a stream of integers. The class should be initialized with an integer k and an initial list of integers. Then, it should support adding new integers to the stream and return the kth largest element after each addition. Input: - An integer k - An initial array of integers nums - A sequence of integers to add to the stream Output: - After each addition, return the kth largest element in the updated stream.

1 ≤ k ≤ 10^40 ≤ nums.length ≤ 10^4-10^4 ≤ nums[i] ≤ 10^4-10^4 ≤ val ≤ 10^4At most 10^4 calls to add()

💡

Example

Input"k = 3, nums = [4, 5, 8, 2]\nadd(3)\nadd(5)\nadd(10)\nadd(9)\nadd(4)"

Output[4, 5, 5, 8, 8]

Initially, the 3rd largest element is 4. After adding 3, the 3rd largest remains 4. Adding 5 updates the 3rd largest to 5. Adding 10 updates it to 5. Adding 9 updates it to 8. Adding 4 keeps it at 8.

k is 1 and nums is empty → returns the largest element seen so far
nums is empty and multiple adds happen → kth largest updates correctly
k is larger than the number of elements in the stream → returns the smallest element in the stream so far
All elements are the same → kth largest is that element

⚠️

Common Mistakes

Sorting entire stream on every add

Time limit exceeded on large inputs

✅ Use a min-heap of size k to maintain kth largest efficiently

Using max-heap instead of min-heap for kth largest

Incorrect kth largest element returned

✅ Use min-heap to keep track of k largest elements, root is kth largest

Not handling initial nums properly

Heap size may exceed k or initial elements ignored

✅ Add initial nums elements using add() logic or heapify and pop excess

Returning wrong index in sorted list approaches

Off-by-one errors cause wrong kth largest

✅ Return element at index len(nums) - k when sorted ascending

Not maintaining heap property after insertion

Heap becomes invalid, wrong results or runtime errors

✅ Use heapify, heap push/pop, or implement heapify up/down correctly

🧠

Brute Force (Sort Entire Stream on Each Add)

💡 This approach exists to establish a baseline understanding. It is simple but inefficient, helping beginners grasp the problem before optimizing.

Intuition

Store all elements seen so far. Each time a new element is added, sort the entire list and pick the kth largest element.

Algorithm

Initialize a list with the given nums.
For each add(val) call, append val to the list.
Sort the list in descending order.
Return the element at index k-1.

💡 The main challenge is realizing that sorting the entire list every time is expensive, but this approach is easy to implement and understand.

</>

Code

class KthLargest:
    def __init__(self, k: int, nums: list[int]):
        self.k = k
        self.nums = nums

    def add(self, val: int) -> int:
        self.nums.append(val)
        self.nums.sort(reverse=True)
        return self.nums[self.k - 1]

# Driver code
if __name__ == '__main__':
    kthLargest = KthLargest(3, [4, 5, 8, 2])
    print(kthLargest.add(3))  # returns 4
    print(kthLargest.add(5))  # returns 5
    print(kthLargest.add(10)) # returns 5
    print(kthLargest.add(9))  # returns 8
    print(kthLargest.add(4))  # returns 8

Line Notes

self.k = kStore k to know which largest element to track

self.nums = numsKeep all numbers seen so far in a list

self.nums.append(val)Add the new value to the list

self.nums.sort(reverse=True)Sort descending to find kth largest easily

return self.nums[self.k - 1]Return the kth largest element after sorting

import java.util.*;

class KthLargest {
    private int k;
    private List<Integer> nums;

    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) {
        nums.add(val);
        Collections.sort(nums, Collections.reverseOrder());
        return nums.get(k - 1);
    }

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

Line Notes

this.k = k;Store k for kth largest tracking

this.nums = new ArrayList<>();Initialize list to hold all numbers

nums.add(val);Add new value to the list

Collections.sort(nums, Collections.reverseOrder());Sort descending to find kth largest

return nums.get(k - 1);Return kth largest element after sorting

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class KthLargest {
    int k;
    vector<int> nums;
public:
    KthLargest(int k, vector<int>& nums) {
        this->k = k;
        this->nums = nums;
    }

    int add(int val) {
        nums.push_back(val);
        sort(nums.rbegin(), nums.rend());
        return nums[k - 1];
    }
};

int main() {
    vector<int> nums = {4, 5, 8, 2};
    KthLargest kthLargest(3, nums);
    cout << kthLargest.add(3) << "\n";  // 4
    cout << kthLargest.add(5) << "\n";  // 5
    cout << kthLargest.add(10) << "\n"; // 5
    cout << kthLargest.add(9) << "\n";  // 8
    cout << kthLargest.add(4) << "\n";  // 8
    return 0;
}

Line Notes

this->k = k;Store k for kth largest element tracking

this->nums = nums;Initialize vector with initial numbers

nums.push_back(val);Add new value to the vector

sort(nums.rbegin(), nums.rend());Sort descending to get kth largest easily

return nums[k - 1];Return kth largest element after sorting

class KthLargest {
    constructor(k, nums) {
        this.k = k;
        this.nums = nums;
    }

    add(val) {
        this.nums.push(val);
        this.nums.sort((a, b) => b - a);
        return this.nums[this.k - 1];
    }
}

// Driver code
const kthLargest = new KthLargest(3, [4, 5, 8, 2]);
console.log(kthLargest.add(3));  // 4
console.log(kthLargest.add(5));  // 5
console.log(kthLargest.add(10)); // 5
console.log(kthLargest.add(9));  // 8
console.log(kthLargest.add(4));  // 8

Line Notes

this.k = k;Store k to track kth largest element

this.nums = nums;Keep all numbers seen so far

this.nums.push(val);Add new value to the array

this.nums.sort((a, b) => b - a);Sort descending to find kth largest

return this.nums[this.k - 1];Return kth largest element after sorting

⏱

Complexity

TimeO(n log n) per add call due to sorting

SpaceO(n) to store all elements

Each add inserts an element and sorts the entire list of size n, which costs O(n log n). Over multiple adds, this becomes very expensive.

💡 For n=10000, sorting each time means about 10000 * 10000 * log(10000) operations, which is too slow for large inputs.

Interview Verdict: TLE for large inputs; only useful to introduce the problem

This approach is too slow for real interviews but helps understand the problem before optimizing.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	`O(n log n) per add`	`O(n)`	No	N/A	Mention only - never code
2. Sorted List with Binary Insertion	`O(n) per add`	`O(n)`	No	N/A	Mention as improvement, but not optimal
3. Min-Heap of Size k	`O(log k) per add`	`O(k)`	No	N/A	Code this approach in 95% of interviews

Practice

(1/5)

1. Consider the following Python code implementing a frequency stack using a max-heap with timestamp. After executing the sequence of operations below, what is the output of the last pop() call?

fs = FreqStack()
fs.push(1)
fs.push(2)
fs.push(1)
print(fs.pop())
print(fs.pop())

easy

A. 1 and then 1

B. 2 and then 1

C. 1 and then 2

D. 2 and then 2

3. Consider the following buggy code for sorting characters by frequency. Which line contains the subtle bug that causes incorrect output?

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(str(count))  # Bug here: appending count instead of repeated char
    return ''.join(result)

medium

A. Line 7: appending characters to buckets

B. Line 10: appending str(count) instead of repeated characters

C. Line 5: max_freq calculation

D. Line 9: iterating freq_count from max_freq down to 1

Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard

Intuition

Algorithm

Intuition

Algorithm

Intuition

Algorithm

How to Present

Time Allocation

What the Interviewer Tests

Common Follow-ups

When to Use

Signature Phrases

NOT This Pattern When

Similar Problems

Practice

Solution

Step 1: Trace push operations

Step 2: Trace pop operations

Final Answer:

Quick Check:

Solution

Step 1: Understand the problem constraints

Step 2: Evaluate approaches for optimality

Final Answer:

Quick Check:

Solution

Step 1: Identify incorrect append operation

Step 2: Why this causes wrong output

Final Answer:

Quick Check:

Solution

Step 1: Understand sorting within buckets

Step 2: Identify incorrect sorting order

Final Answer:

Quick Check:

Solution

Step 1: Understand duplicates impact

Step 2: Modify partition to handle duplicates correctly

Final Answer:

Quick Check:

Ready to prove it?