Forgetting null/base-case handling
Wrong move: Recursive traversal assumes children always exist.
Usually fails on: Leaf nodes throw errors or create wrong depth/path values.
Fix: Handle null/base cases before recursive transitions.
Build confidence with an intuition-first walkthrough focused on tree fundamentals.
You are part of a university admissions office and need to keep track of the kth highest test score from applicants in real-time. This helps to determine cut-off marks for interviews and admissions dynamically as new applicants submit their scores.
You are tasked to implement a class which, for a given integer k, maintains a stream of test scores and continuously returns the kth highest test score after a new score has been submitted. More specifically, we are looking for the kth highest score in the sorted list of all scores.
Implement the KthLargest class:
KthLargest(int k, int[] nums) Initializes the object with the integer k and the stream of test scores nums.int add(int val) Adds a new test score val to the stream and returns the element representing the kth largest element in the pool of test scores so far.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
Example 2:
Input:
["KthLargest", "add", "add", "add", "add"]
[[4, [7, 7, 7, 7, 8, 3]], [2], [10], [9], [9]]
Output: [null, 7, 7, 7, 8]
Explanation:
KthLargest kthLargest = new KthLargest(4, [7, 7, 7, 7, 8, 3]);Constraints:
0 <= nums.length <= 1041 <= k <= nums.length + 1-104 <= nums[i] <= 104-104 <= val <= 104104 calls will be made to add.Problem summary: You are part of a university admissions office and need to keep track of the kth highest test score from applicants in real-time. This helps to determine cut-off marks for interviews and admissions dynamically as new applicants submit their scores. You are tasked to implement a class which, for a given integer k, maintains a stream of test scores and continuously returns the kth highest test score after a new score has been submitted. More specifically, we are looking for the kth highest score in the sorted list of all scores. Implement the KthLargest class: KthLargest(int k, int[] nums) Initializes the object with the integer k and the stream of test scores nums. int add(int val) Adds a new test score val to the stream and returns the element representing the kth largest element in the pool of test scores so far.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Tree · Design
["KthLargest","add","add","add","add","add"] [[3,[4,5,8,2]],[3],[5],[10],[9],[4]]
["KthLargest","add","add","add","add"] [[4,[7,7,7,7,8,3]],[2],[10],[9],[9]]
kth-largest-element-in-an-array)finding-mk-average)sequentially-ordinal-rank-tracker)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #703: Kth Largest Element in a Stream
class KthLargest {
private PriorityQueue<Integer> minQ;
private int k;
public KthLargest(int k, int[] nums) {
this.k = k;
minQ = new PriorityQueue<>(k);
for (int x : nums) {
add(x);
}
}
public int add(int val) {
minQ.offer(val);
if (minQ.size() > k) {
minQ.poll();
}
return minQ.peek();
}
}
/**
* Your KthLargest object will be instantiated and called as such:
* KthLargest obj = new KthLargest(k, nums);
* int param_1 = obj.add(val);
*/
// Accepted solution for LeetCode #703: Kth Largest Element in a Stream
type KthLargest struct {
k int
minQ hp
}
func Constructor(k int, nums []int) KthLargest {
minQ := hp{}
this := KthLargest{k, minQ}
for _, x := range nums {
this.Add(x)
}
return this
}
func (this *KthLargest) Add(val int) int {
heap.Push(&this.minQ, val)
if this.minQ.Len() > this.k {
heap.Pop(&this.minQ)
}
return this.minQ.IntSlice[0]
}
type hp struct{ sort.IntSlice }
func (h *hp) Less(i, j int) bool { return h.IntSlice[i] < h.IntSlice[j] }
func (h *hp) Pop() interface{} {
old := h.IntSlice
n := len(old)
x := old[n-1]
h.IntSlice = old[0 : n-1]
return x
}
func (h *hp) Push(x interface{}) {
h.IntSlice = append(h.IntSlice, x.(int))
}
/**
* Your KthLargest object will be instantiated and called as such:
* obj := Constructor(k, nums);
* param_1 := obj.Add(val);
*/
# Accepted solution for LeetCode #703: Kth Largest Element in a Stream
class KthLargest:
def __init__(self, k: int, nums: List[int]):
self.k = k
self.min_q = []
for x in nums:
self.add(x)
def add(self, val: int) -> int:
heappush(self.min_q, val)
if len(self.min_q) > self.k:
heappop(self.min_q)
return self.min_q[0]
# Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)
// Accepted solution for LeetCode #703: Kth Largest Element in a Stream
use std::{cmp::Reverse, collections::BinaryHeap};
struct KthLargest {
min_heap: BinaryHeap<Reverse<i32>>,
size: usize,
}
impl KthLargest {
fn new(k: i32, nums: Vec<i32>) -> Self {
let mut kth_largest = KthLargest {
min_heap: BinaryHeap::new(),
size: k as usize,
};
for n in nums {
kth_largest.add(n);
}
kth_largest
}
fn add(&mut self, val: i32) -> i32 {
self.min_heap.push(Reverse(val));
if self.min_heap.len() > self.size {
self.min_heap.pop();
}
match self.min_heap.peek() {
Some(Reverse(min_val)) => *min_val,
_ => -1,
}
}
}
// Accepted solution for LeetCode #703: Kth Largest Element in a Stream
class KthLargest {
#k: number = 0;
#minQ = new MinPriorityQueue<number>();
constructor(k: number, nums: number[]) {
this.#k = k;
for (const x of nums) {
this.add(x);
}
}
add(val: number): number {
this.#minQ.enqueue(val);
if (this.#minQ.size() > this.#k) {
this.#minQ.dequeue();
}
return this.#minQ.front();
}
}
/**
* Your KthLargest object will be instantiated and called as such:
* var obj = new KthLargest(k, nums)
* var param_1 = obj.add(val)
*/
Use this to step through a reusable interview workflow for this problem.
BFS with a queue visits every node exactly once — O(n) time. The queue may hold an entire level of the tree, which for a complete binary tree is up to n/2 nodes = O(n) space. This is optimal in time but costly in space for wide trees.
Every node is visited exactly once, giving O(n) time. Space depends on tree shape: O(h) for recursive DFS (stack depth = height h), or O(w) for BFS (queue width = widest level). For balanced trees h = log n; for skewed trees h = n.
Review these before coding to avoid predictable interview regressions.
Wrong move: Recursive traversal assumes children always exist.
Usually fails on: Leaf nodes throw errors or create wrong depth/path values.
Fix: Handle null/base cases before recursive transitions.