PPractick

The problem

A leaderboard service must quickly report the k-th highest score among n players without fully sorting all scores. Keep a min-heap of the k largest values seen so far. Its root is the smallest of those k, which is exactly the k-th largest, and any new score bigger than the root replaces it. That's O(n log k) time and O(k) memory, and it also works when the scores arrive as a stream. Quickselect is the O(n)-average alternative.

Example: [3, 2, 1, 5, 6, 4], k = 2 → 5.

Function signature

int findKthLargest(const vector<int>& nums, int k);  // 1 <= k <= n

Test cases

Input (nums, k)	Output	Explanation
([3, 2, 1, 5, 6, 4], 2)	5
([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)	4	Duplicates count: 6, 5, 5, 4
([1], 1)	1
([7, 7, 7], 2)	7
([-1, -5, 3], 3)	-5	The 3rd largest is the minimum

(Confirm: the k-th largest in sorted order, not the k-th distinct value.)

How interviewers phrase it

• "Given an integer array and k, return the k-th largest element in the array" (LeetCode 215), often with "can you do it without sorting?"

Clarifying questions to ask

1. The k-th largest counting duplicates, or the k-th distinct? (Counting duplicates.)
2. Can the array be modified? (That matters for quickselect.)
3. Is it a one-off query or a stream? (A heap works for streams.)

Follow-ups to expect

1. "Why a min-heap and not a max-heap?"
2. "When do you replace the root?"
3. "Quickselect?"
4. "Guaranteed O(n)?"
5. "Complexity of the heap approach?"

Related questions

• Implement Min Heap Medium
• Check if an array represents a min heap Medium
• Convert Min Heap to Max Heap Medium
• Kth smallest element in an array [use priority queue] Medium
• Task Scheduler Medium
• Hand of Straights Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in