Kth Largest Element in an Array (LeetCode 215)
nums is an integer array and k is an integer. Find the value that would sit in position k if the array were sorted from largest to smallest — this counts every occurrence of a duplicate value separately, not just distinct values, so a repeated value can fill more than one of those ranked positions.
Bonus challenge: can you find it without fully sorting the array?
Worked Examples
nums = [3,2,1,5,6,4], k = 256, 5, 4, 3, 2, 1. The 2nd is 5.nums = [3,2,3,1,2,4,5,5,6], k = 446, 5, 5, 4, .... Equal values count separately, so the 4th is 4.⚖️Formal Constraints & Bounds
1 <= k <= nums.length <= 105-104 <= nums[i] <= 104
Core Insight
A partition puts every copy of the pivot exactly where sorting would, so comparing target = len(nums) - k with the equal block nums[lt..gt] says which one side can still hold the answer; the other side is never read again.
Real-World Scenario & Production Applications
Picking the 95th- or 99th-percentile latency out of one batch of request timings, choosing a median split value when building a k-d tree, and computing a score cut-off (the 1000th-best score) before paging through results.
Subproblems & Recurrence Decomposition3 Phases
The k-th largest value sits at index target = len(nums) - k of the ascending order; the search window nums[lo..hi] always holds it.
target = len(nums) - k
lo, hi = 0, len(nums) - 1Step-by-Step Execution Trace Table
| Pass | Searched nums[lo..hi] | Random pivot | nums after the partition | Equal block nums[lt..gt] | target = 4 is | Next |
|---|---|---|---|---|---|---|
| 1 | nums[0..5] | 1 | [1, 2, 5, 6, 4, 3] | nums[0..0] | right of gt | lo = gt + 1 = 1 |
| 2 | nums[1..5] | 6 | [1, 2, 5, 4, 3, 6] | nums[5..5] | left of lt | hi = lt - 1 = 4 |
| 3 | nums[1..4] | 3 | [1, 2, 3, 4, 5, 6] | nums[2..2] | right of gt | lo = gt + 1 = 3 |
| 4 | nums[3..4] | 5 | [1, 2, 3, 4, 5, 6] | nums[4..4] | inside | return 5 |
| 1 | target = len(nums) - k |
| 2 | lo, hi = 0, len(nums) - 1 |
| 3 | while True: |
| 4 | pivot = nums[random.randint(lo, hi)] |
| 5 | lt, i, gt = lo, lo, hi |
| 6 | while i <= gt: |
| 7 | if nums[i] < pivot: |
| 8 | nums[lt], nums[i] = nums[i], nums[lt] |
| 9 | lt += 1 |
| 10 | i += 1 |
| 11 | elif nums[i] > pivot: |
| 12 | nums[i], nums[gt] = nums[gt], nums[i] |
| 13 | gt -= 1 |
| 14 | else: |
| 15 | i += 1 |
| 16 | if target < lt: |
| 17 | hi = lt - 1 |
| 18 | elif target > gt: |
| 19 | lo = gt + 1 |
| 20 | else: |
| 21 | return pivot |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Sorting the whole array to read one position does far more work than the question needs: it puts every value in order, when only the value at index n - k matters. Quickselect runs one partition step of quicksort and then follows only the side that holds that index. The other side is never looked at again, so each pass works on a smaller range than the last.
🏀 The Analogy: The 2nd-Tallest Player Without Lining Up the Team
A coach wants the 2nd-tallest player of a team of 20. Lining everyone up by height works, but it orders 20 people to learn one fact. Instead, pick one player at random and split the team: shorter players to one side, the same height in the middle, taller players to the other side. If 5 players are taller than the one you picked, the 2nd-tallest is among those 5: send everyone else home and repeat with the 5. If exactly 1 player is taller, the one you picked is the answer.
🔑 The Key Idea in the Code
Every copy of pivot ends up in nums[lt..gt], exactly the indices sorting would give it, so comparing target with lt and gt tells you which side can hold the answer. The random pivot matters: a fixed nums[hi] on an already sorted input is always the largest value, each split removes a single value, and the run turns quadratic.
🏔️ When the Heap Is the Better Tool
The Top-K Heap solution (the second tab) keeps a min-heap of the k largest values seen so far. It runs in O(N log K) time and O(K) space, has no bad input, never changes nums and never needs all the values at once, so it wins when values stream in or the input must stay untouched. Quickselect wins when every value is already in memory, the array may be rearranged, and one answer is needed: O(N) time on average with O(1) extra space.
Using the fixed pivot
nums[hi]instead of a random oneSetting
target = k - 1for the k-th largestPutting values equal to
pivotinto the smaller blockMoving
iforward after swapping withnums[gt]
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
The statement asks for one value at one rank ("the value that would sit in position k if the array were sorted from largest to smallest") and adds "can you find it without fully sorting the array?". Every value is given at once, nothing streams in, and only one answer is needed: that is the signal for selection, not for a sort or a heap that is kept up to date.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: target = len(nums) - k always lies in nums[lo..hi]. After each partition nums[lo..lt-1] is smaller than pivot, nums[lt..gt] equals it and nums[gt+1..hi] is larger, so the copies of pivot sit at their sorted places. Decision: target < lt keeps the left block (hi = lt - 1), target > gt keeps the right block (lo = gt + 1), otherwise return pivot.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Fixed pivot:
pivot = nums[hi]is always the largest value of a sorted input, so each pass drops one value and the run becomes O(N^2); usepivot = nums[random.randint(lo, hi)].Rank to index: the k-th largest is at
target = len(nums) - kof the ascending order;k - 1finds the k-th smallest.Two-way partition: without the middle block
nums[lt..gt], an array of equal values also shrinks by one value per pass.After
nums[i], nums[gt] = nums[gt], nums[i]onlygt -= 1: the value that arrived atnums[i]has not been compared withpivotyet.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'll use Quickselect. Sorted ascending, the k-th largest sits at index n minus k, so that is my target, and I never need the rest of the order. I pick a random pivot and partition the current range into three blocks: smaller than the pivot, equal to it, and larger. After that, every copy of the pivot sits exactly where sorting would put it, so if the target falls inside the equal block, the pivot is the answer. If the target is left of it, I keep only the smaller block; if it is right of it, only the larger one. The other side is never read again. The trap is the pivot: a fixed last element is always the maximum of a sorted input, every pass drops one value, and the run goes quadratic. A random pivot discards a constant fraction of the range on average. The three-way split also handles many equal values. That gives
O(N)time on average, O(N squared) in the rare worst case, andO(1)extra space, since I partition in place."
Complexity & Mathematical Proof
O(N) average, O(N^2) worst case
Look at the code: one pass of while True runs the inner while i <= gt loop once per value of nums[lo..hi], and each iteration does one comparison and at most one swap, so a pass over a range of size m costs about m steps. After the pass, hi = lt - 1 or lo = gt + 1 keeps only one side. A random pivot lands in the middle half of the range with probability 1/2, and then the kept side has at most 3m/4 values, so on average the ranges shrink geometrically: N + 3N/4 + (3/4)^2 N + ... is at most 4N, a constant times N (a finer count gives about 2N to 3.4N comparisons). The worst case is a pivot that is the smallest or largest value every time: then each pass removes one value and the passes cost N + (N - 1) + ... + 1 = O(N^2). A random pivot makes that as unlikely as flipping the same coin side N times.
O(1)
Look at the allocations: the partition swaps values inside nums itself. Besides it the code keeps target, lo, hi, pivot, lt, i and gt: seven integers, whatever N is. The loop is iterative (while True), so there is no recursion stack.
E[T(N)] <= N + (3/4)N + (3/4)^2 N + ... <= 4N = O(N); worst case T(N) = N + (N - 1) + ... + 1 = O(N^2)
Derivation Progression
while i <= gt: 1 comparison + at most 1 swap per value -> m steps
Every step either moves i forward or gt back, so the unread range nums[i..gt] shrinks by one each time: exactly m steps per pass.
hi = lt - 1 or lo = gt + 1 -> the next m is one block
Only the block holding target is searched again; the equal block and the other side are dropped for good.
P(pivot in the middle half) = 1/2 -> kept side <= 3m/4 every 2 passes on average
The ranges shrink geometrically, so the total work is a geometric series bounded by a constant times N.
pivot = min or max every pass -> N + (N - 1) + ... + 1 = N(N + 1)/2
This is what a fixed nums[hi] pivot does on sorted input every time; with a random pivot it needs an extremely unlucky run.
Variable Definitions
len(nums), the number of values
hi - lo + 1, the size of the range one pass partitions
Memory Architecture & Bounds
O(1): the loop is iterative, no recursion
O(1): the integers target, lo, hi, pivot, lt, i and gt
O(1): one integer
Boundary Best / Worst Cases
: the first pivot's equal block already holds target, one pass
with a random pivot, on any input
: the pivot is the smallest or largest value in every pass
Binary Heap Priority Queue Tree
Senior SWE Deconstruction & Hardware Caveats
Scale signal: one rank of one in-memory array, asked once. Sorting costs and a heap of size costs , while Quickselect averages ; the heap wins back when values stream in and can't all be stored.
, : at most distinct values among , so duplicates are common, and the three-way split keeps them from slowing the passes.
In a service, any deterministic pivot rule lets an attacker choose inputs that force the quadratic case, a denial-of-service lever; a random pivot (or median-of-medians when a hard worst-case bound is required) removes it. Quickselect rearranges its input: copy the array first if callers still need the original order.
Core Algorithmic State Invariants
- The Two Ends
k = 1 gives target = len(nums) - 1, the maximum, and k = len(nums) gives target = 0, the minimum: the same loop covers both, with no special case.
Kth Largest Element in an Array (LeetCode 215)
nums is an integer array and k is an integer. Find the value that would sit in position k if the array were sorted from largest to smallest — this counts every occurrence of a duplicate value separately, not just distinct values, so a repeated value can fill more than one of those ranked positions.
Bonus challenge: can you find it without fully sorting the array?
Worked Examples
nums = [3,2,1,5,6,4], k = 256, 5, 4, 3, 2, 1. The 2nd is 5.nums = [3,2,3,1,2,4,5,5,6], k = 446, 5, 5, 4, .... Equal values count separately, so the 4th is 4.⚖️Formal Constraints & Bounds
1 <= k <= nums.length <= 105-104 <= nums[i] <= 104
Core Insight
A partition puts every copy of the pivot exactly where sorting would, so comparing target = len(nums) - k with the equal block nums[lt..gt] says which one side can still hold the answer; the other side is never read again.
Real-World Scenario & Production Applications
Picking the 95th- or 99th-percentile latency out of one batch of request timings, choosing a median split value when building a k-d tree, and computing a score cut-off (the 1000th-best score) before paging through results.
Subproblems & Recurrence Decomposition3 Phases
The k-th largest value sits at index target = len(nums) - k of the ascending order; the search window nums[lo..hi] always holds it.
target = len(nums) - k
lo, hi = 0, len(nums) - 1Step-by-Step Execution Trace Table
| Pass | Searched nums[lo..hi] | Random pivot | nums after the partition | Equal block nums[lt..gt] | target = 4 is | Next |
|---|---|---|---|---|---|---|
| 1 | nums[0..5] | 1 | [1, 2, 5, 6, 4, 3] | nums[0..0] | right of gt | lo = gt + 1 = 1 |
| 2 | nums[1..5] | 6 | [1, 2, 5, 4, 3, 6] | nums[5..5] | left of lt | hi = lt - 1 = 4 |
| 3 | nums[1..4] | 3 | [1, 2, 3, 4, 5, 6] | nums[2..2] | right of gt | lo = gt + 1 = 3 |
| 4 | nums[3..4] | 5 | [1, 2, 3, 4, 5, 6] | nums[4..4] | inside | return 5 |
| 1 | target = len(nums) - k |
| 2 | lo, hi = 0, len(nums) - 1 |
| 3 | while True: |
| 4 | pivot = nums[random.randint(lo, hi)] |
| 5 | lt, i, gt = lo, lo, hi |
| 6 | while i <= gt: |
| 7 | if nums[i] < pivot: |
| 8 | nums[lt], nums[i] = nums[i], nums[lt] |
| 9 | lt += 1 |
| 10 | i += 1 |
| 11 | elif nums[i] > pivot: |
| 12 | nums[i], nums[gt] = nums[gt], nums[i] |
| 13 | gt -= 1 |
| 14 | else: |
| 15 | i += 1 |
| 16 | if target < lt: |
| 17 | hi = lt - 1 |
| 18 | elif target > gt: |
| 19 | lo = gt + 1 |
| 20 | else: |
| 21 | return pivot |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Sorting the whole array to read one position does far more work than the question needs: it puts every value in order, when only the value at index n - k matters. Quickselect runs one partition step of quicksort and then follows only the side that holds that index. The other side is never looked at again, so each pass works on a smaller range than the last.
🏀 The Analogy: The 2nd-Tallest Player Without Lining Up the Team
A coach wants the 2nd-tallest player of a team of 20. Lining everyone up by height works, but it orders 20 people to learn one fact. Instead, pick one player at random and split the team: shorter players to one side, the same height in the middle, taller players to the other side. If 5 players are taller than the one you picked, the 2nd-tallest is among those 5: send everyone else home and repeat with the 5. If exactly 1 player is taller, the one you picked is the answer.
🔑 The Key Idea in the Code
Every copy of pivot ends up in nums[lt..gt], exactly the indices sorting would give it, so comparing target with lt and gt tells you which side can hold the answer. The random pivot matters: a fixed nums[hi] on an already sorted input is always the largest value, each split removes a single value, and the run turns quadratic.
🏔️ When the Heap Is the Better Tool
The Top-K Heap solution (the second tab) keeps a min-heap of the k largest values seen so far. It runs in O(N log K) time and O(K) space, has no bad input, never changes nums and never needs all the values at once, so it wins when values stream in or the input must stay untouched. Quickselect wins when every value is already in memory, the array may be rearranged, and one answer is needed: O(N) time on average with O(1) extra space.
Using the fixed pivot
nums[hi]instead of a random oneSetting
target = k - 1for the k-th largestPutting values equal to
pivotinto the smaller blockMoving
iforward after swapping withnums[gt]
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
The statement asks for one value at one rank ("the value that would sit in position k if the array were sorted from largest to smallest") and adds "can you find it without fully sorting the array?". Every value is given at once, nothing streams in, and only one answer is needed: that is the signal for selection, not for a sort or a heap that is kept up to date.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: target = len(nums) - k always lies in nums[lo..hi]. After each partition nums[lo..lt-1] is smaller than pivot, nums[lt..gt] equals it and nums[gt+1..hi] is larger, so the copies of pivot sit at their sorted places. Decision: target < lt keeps the left block (hi = lt - 1), target > gt keeps the right block (lo = gt + 1), otherwise return pivot.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Fixed pivot:
pivot = nums[hi]is always the largest value of a sorted input, so each pass drops one value and the run becomes O(N^2); usepivot = nums[random.randint(lo, hi)].Rank to index: the k-th largest is at
target = len(nums) - kof the ascending order;k - 1finds the k-th smallest.Two-way partition: without the middle block
nums[lt..gt], an array of equal values also shrinks by one value per pass.After
nums[i], nums[gt] = nums[gt], nums[i]onlygt -= 1: the value that arrived atnums[i]has not been compared withpivotyet.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'll use Quickselect. Sorted ascending, the k-th largest sits at index n minus k, so that is my target, and I never need the rest of the order. I pick a random pivot and partition the current range into three blocks: smaller than the pivot, equal to it, and larger. After that, every copy of the pivot sits exactly where sorting would put it, so if the target falls inside the equal block, the pivot is the answer. If the target is left of it, I keep only the smaller block; if it is right of it, only the larger one. The other side is never read again. The trap is the pivot: a fixed last element is always the maximum of a sorted input, every pass drops one value, and the run goes quadratic. A random pivot discards a constant fraction of the range on average. The three-way split also handles many equal values. That gives
O(N)time on average, O(N squared) in the rare worst case, andO(1)extra space, since I partition in place."
Complexity & Mathematical Proof
O(N) average, O(N^2) worst case
Look at the code: one pass of while True runs the inner while i <= gt loop once per value of nums[lo..hi], and each iteration does one comparison and at most one swap, so a pass over a range of size m costs about m steps. After the pass, hi = lt - 1 or lo = gt + 1 keeps only one side. A random pivot lands in the middle half of the range with probability 1/2, and then the kept side has at most 3m/4 values, so on average the ranges shrink geometrically: N + 3N/4 + (3/4)^2 N + ... is at most 4N, a constant times N (a finer count gives about 2N to 3.4N comparisons). The worst case is a pivot that is the smallest or largest value every time: then each pass removes one value and the passes cost N + (N - 1) + ... + 1 = O(N^2). A random pivot makes that as unlikely as flipping the same coin side N times.
O(1)
Look at the allocations: the partition swaps values inside nums itself. Besides it the code keeps target, lo, hi, pivot, lt, i and gt: seven integers, whatever N is. The loop is iterative (while True), so there is no recursion stack.
E[T(N)] <= N + (3/4)N + (3/4)^2 N + ... <= 4N = O(N); worst case T(N) = N + (N - 1) + ... + 1 = O(N^2)
Derivation Progression
while i <= gt: 1 comparison + at most 1 swap per value -> m steps
Every step either moves i forward or gt back, so the unread range nums[i..gt] shrinks by one each time: exactly m steps per pass.
hi = lt - 1 or lo = gt + 1 -> the next m is one block
Only the block holding target is searched again; the equal block and the other side are dropped for good.
P(pivot in the middle half) = 1/2 -> kept side <= 3m/4 every 2 passes on average
The ranges shrink geometrically, so the total work is a geometric series bounded by a constant times N.
pivot = min or max every pass -> N + (N - 1) + ... + 1 = N(N + 1)/2
This is what a fixed nums[hi] pivot does on sorted input every time; with a random pivot it needs an extremely unlucky run.
Variable Definitions
len(nums), the number of values
hi - lo + 1, the size of the range one pass partitions
Memory Architecture & Bounds
O(1): the loop is iterative, no recursion
O(1): the integers target, lo, hi, pivot, lt, i and gt
O(1): one integer
Boundary Best / Worst Cases
: the first pivot's equal block already holds target, one pass
with a random pivot, on any input
: the pivot is the smallest or largest value in every pass
Binary Heap Priority Queue Tree
Senior SWE Deconstruction & Hardware Caveats
Scale signal: one rank of one in-memory array, asked once. Sorting costs and a heap of size costs , while Quickselect averages ; the heap wins back when values stream in and can't all be stored.
, : at most distinct values among , so duplicates are common, and the three-way split keeps them from slowing the passes.
In a service, any deterministic pivot rule lets an attacker choose inputs that force the quadratic case, a denial-of-service lever; a random pivot (or median-of-medians when a hard worst-case bound is required) removes it. Quickselect rearranges its input: copy the array first if callers still need the original order.
Core Algorithmic State Invariants
- The Two Ends
k = 1 gives target = len(nums) - 1, the maximum, and k = len(nums) gives target = 0, the minimum: the same loop covers both, with no special case.