DSA · Heap / Quickselect · #95
Kth Largest Element in an Array
Module 70 · difficulty 3/5·⏱ 30:00starts on first keystroke
Given an integer array `nums` and an integer `k`, return the **kth largest** element in the array. Note that it is the kth largest element in **sorted order**, not the kth distinct element. Duplicates count toward the ordering. Implement the function `findKthLargest(nums, k)` which returns a number. Try to solve it without fully sorting, ideally in O(n) average time.
Examples
nums = [3,2,1,5,6,4], k = 2→5— Sorted descending: [6,5,4,3,2,1]; the 2nd largest is 5.nums = [3,2,3,1,2,4,5,5,6], k = 4→4— Duplicates count: sorted descending [6,5,5,4,4,3,3,2,2,1...]; the 4th largest is 4.nums = [1], k = 1→1— Single element is both the largest and the kth largest.
Constraints
- · 1 <= k <= nums.length <= 10^5
- · -10^4 <= nums[i] <= 10^4
- · The answer is guaranteed to exist (k is within bounds).
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.