Coding Interview PatternsKth Largest Element in an Array
MediumTop K Elements

Kth Largest Element in an Array

Explanation & Solution

Practice Problem

Description

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.

Can you solve it without sorting?

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

Output: 5

Explanation: The sorted array is [1, 2, 3, 4, 5, 6]. The 2nd largest element is 5.

Constraints

  • 1 <= k <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4

Approach

Top K Elements pattern

1. Reframe the Problem

  • The kth largest element is the same as the (n - k)th smallest element (0-indexed) when the array is sorted in ascending order.
  • Set target = nums.length - k to convert the problem into finding the element at index target in a sorted array.

2. Choose a Pivot

  • Pick the last element in the current sub-array as the pivot.
  • This keeps the partition logic simple and avoids extra index calculations.

3. Partition the Sub-array

  • Maintain a store pointer starting at left.
  • Iterate through the sub-array from left to right - 1.
  • Whenever an element is less than or equal to the pivot, swap it with the element at store and increment store.
  • After the loop, swap the pivot into its final sorted position at store.

4. Recurse on One Side Only

  • If store === target, the pivot is the answer — return it immediately.
  • If store < target, the answer lies in the right partition — recurse on [store + 1, right].
  • If store > target, the answer lies in the left partition — recurse on [left, store - 1].

5. Return the Result

  • Each recursive call eliminates at least one element (the pivot), and we only recurse into one side.
  • On average, the search space halves each time, leading to linear average-case performance.

Key Insight

  • The key idea is that we do not need to fully sort the array — we only need to find the element that would sit at one specific index, which Quickselect does efficiently by discarding half the remaining elements on average each iteration.
Time
O(n) average, O(n²) worst case. Quickselect partitions the array and only recurses into the half containing the target index, giving expected linear time.
Space
O(1) extra space (in-place partitioning) with O(log n) recursion stack on average.

Visualization

Input:
[3, 2, 1, 5, 6, 4], k = 2
302112536445
—

No animation available

Left (L)Right (R)ConvergedDone
0 steps

Solution Code

Next
Top K Frequent Elements