DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Kth Largest Element in an Array

mediumHeaps and top-K Must-do

Problem statement

Given an unsorted array of integers nums and an integer k, return the k-th largest value in the array. This is the value that would sit at position k if the array were sorted from largest to smallest, so duplicates count separately: in [4, 4, 1], both the first and second largest are 4.

k is always between 1 and the length of the array. Try to do better than sorting the whole array.

Examples

Example 1

Input: nums = [7, 2, 9, 4, 4, 1], k = 2

Output: 7

Explanation: From largest to smallest the values are 9, 7, 4, 4, 2, 1. The second is 7.

Example 2

Input: nums = [3, 8, 8, 5, 1], k = 4

Output: 3

Explanation: Largest to smallest: 8, 8, 5, 3, 1. The two 8s count as separate positions, so the fourth is 3.

Hints

Approach

Use quickselect: quicksort's partition, but only follow the side that contains the answer.

  1. The k-th largest is the element at index n - k in ascending order. Call that target.
  2. Pick a random pivot and partition the current range into three blocks: less than, equal to, and greater than the pivot.
  3. If target falls in the equal block, the pivot is the answer. If it falls in the smaller block, continue only there; otherwise continue only in the larger block.

Each round discards, on average, a constant fraction of the range, so the total work is n + n/2 + n/4 + ..., which is linear on average. The random pivot makes the O(n^2) worst case very unlikely, and the three-way partition keeps arrays full of duplicates fast.

ComplexityTime O(n) average, O(n^2) worst caseSpace O(n) for the working copy (O(1) if you may modify the input)
Python
import random
class Solution:
def findKthLargest(self, nums: list[int], k: int) -> int:
target = len(nums) - k # index of the answer in ascending order
lo, hi = 0, len(nums) - 1
nums = list(nums)
while True:
pivot = nums[random.randint(lo, hi)]
# three-way partition of nums[lo..hi]: < pivot | == pivot | > pivot
lt, i, gt = lo, lo, hi
while i <= gt:
if nums[i] < pivot:
nums[lt], nums[i] = nums[i], nums[lt]
lt += 1
i += 1
elif nums[i] > pivot:
nums[i], nums[gt] = nums[gt], nums[i]
gt -= 1
else:
i += 1
if target < lt:
hi = lt - 1 # answer is among the smaller values
elif target > gt:
lo = gt + 1 # answer is among the larger values
else:
return pivot # target falls in the block equal to pivot

Follow-up questions

  • The numbers arrive as a stream too large to store. Which approach still works?
  • Return the k largest values themselves, not just the k-th.

Frequently asked questions

State sorting first, then the heap, since it is reliable and easy to code. Offer quickselect as the average-linear option, and mention its worst case. Many interviewers are happy with the heap and ask for quickselect only as a follow-up.

With a two-way partition, an array where many values equal the pivot can split very unevenly, which pushes quickselect toward its quadratic worst case. Grouping all pivot-equal values together lets one round skip past all of them at once.

Percentiles are the same question: the p99 latency of 10,000 requests is roughly the 100th largest value. Quickselect finds it without sorting everything, and the size-k heap does it over a live stream of request timings.