Kth Largest

Return the k-th largest element in the array (1-indexed: k=1 is the maximum). Assume 1 <= k <= len(nums).

kthLargest(nums, k)

Input format: nums | k.

Examples

[3, 2, 1, 5, 6, 4], k=2   // → 5
[3, 2, 3, 1, 2, 4, 5, 5, 6], k=4   // → 4
[1], k=1                  // → 1

Walkthrough

Thinking it through

The obvious approach: sort descending, read off index k-1. Correct, but it does more work than needed — full sorting establishes order among every element when you only need one specific rank.

Why sorting is doing extra work

Sorting costs O(n log n) because it figures out the relative order of all n elements, including relationships you'll never use (is the 37th largest bigger than the 52nd?). If k is small relative to n, most of that effort is wasted.

A better approach: track only the candidates that matter

Maintain a running min-heap of just the k largest values seen so far:

Feed elements into a size-k min-heap.
Once it holds k elements, its root is the smallest of your current top-k candidates.
For each new element: bigger than the root means it deserves a spot — evict the root, insert the new one. Smaller or equal means it can't be in the top k — ignore it.
After the scan, the heap holds exactly the k largest, and its root is the k-th largest.

Why this is faster

A heap of size k gives O(log k) insertion and removal, bounded by log k rather than log n. Across n elements: O(n log k) total — better than O(n log n) whenever k is much smaller than n.

Why a heap and not a sorted list of k items

A sorted array of k candidates would cost O(k) per insert/evict (shifting), giving O(nk) overall — worse than O(n log k) for larger k. The heap's weaker "only track the minimum" guarantee is exactly what keeps both operations cheap.

main.py

Auto-saved

Console

Press Run to execute your code, or Submit to test and complete this problem.