What signals in a problem statement indicate the Kth element sub-pattern?

"kth largest element"; "k largest elements"; "repeatedly take the two heaviest stones"

Kth element (Heap — Top K Sub-pattern)

Q: What makes Kth element different from other sub-patterns?

**Last Stone Weight** isn't top K at all: it's "always take the largest", so a full **max-heap** of every stone. **K Largest Elements** and **Kth Largest** keep a **min-heap of size K**; duplicates count separately, so the 4th largest of `[3,2,3,1,2,4,5,5,6]` is 4. **Kth Largest Integer** is the same heap with strings: compare by **length first**, then as strings, because `"9" > "10"` as text.

Find the Kth largest (or the K largest) in an unsorted collection, or keep pulling the current largest out.

Signals in the problem statement

›
"kth largest element"
›
"k largest elements"
›
"repeatedly take the two heaviest stones"

What makes it different

Last Stone Weight isn't top K at all: it's "always take the largest", so a full max-heap of every stone. K Largest Elements and Kth Largest keep a min-heap of size K; duplicates count separately, so the 4th largest of [3,2,3,1,2,4,5,5,6] is 4. Kth Largest Integer is the same heap with strings: compare by length first, then as strings, because "9" > "10" as text.

Questions

ordered from “learn the idea” to “recognise it without help”

1
Last Stone Weight
Basic Anchor·LeetCode #1046
WalkthroughEasy
2
K Largest Elements
Basic Reinforcement·GeeksforGeeks
WalkthroughEasy
3
Kth Largest Element in an Array
Slight Variation·LeetCode #215
WalkthroughMedium
4
Find the Kth Largest Integer in the Array
Medium·LeetCode #1985
WalkthroughMedium

Template

kth-largest-template.cpp

// Kth largest: keep the k largest seen so far in a min-heap of size k.
int findKthLargest(vector<int>& nums, int k) {
    priority_queue<int, vector<int>, greater<int>> pq;     // min-heap: top = weakest of the k
    for (int x : nums) {
        pq.push(x);
        if ((int)pq.size() > k) pq.pop();                   // kick out the smallest
    }
    return pq.top();                                        // the kth largest
}

Remember this · Heap — Top K

Trigger

"K largest / smallest / most frequent / closest", kth element, streaming top-K.

Think

Do I really need everything sorted, or only the best K?

Key question

Min-heap or max-heap of size K — which one lets me kick out the worst candidate?

Heap — Top K overview Top K by frequency