Kth Largest Element in an Array

1. Define the problem

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. Solve it without fully sorting the array, using quickselect : partition around a pivot and recurse into only the side that contains the answer.

Constraints

1 ≤ k ≤ nums.length ≤ 10⁵
-10⁴ ≤ nums_i ≤ 10⁴

Example

Inputnums = [3, 2, 1, 5, 6, 4], k = 2

Output5

Explanation Sorted ascending the array is [1, 2, 3, 4, 5, 6]; the 2nd largest value is 5.

2. Know the words first

In plain terms

Quickselect: A quick sort partition step reused to find a single ranked element, without sorting the rest of the array.

3. Visualize the solution

Partition, then recurse into only the side holding the answer

Statusstart

Partition the whole array around pivot 4 (last element).

What happens in this step

array: [3, 2, 1, 5, 6, 4], k = 2 → target index = length - k = 6 - 2 = 4
pivot = arr[5] = 4 (last element)

Looking for whichever element ends up at index 4 once partitioned — that value is the 2nd largest.

Step 1 of 4

Steps to visualize

Pick a pivot and partition the array around it, same as in quick sort.
The pivot lands at its final sorted index p.
If p equals the target index, the pivot itself is the answer — stop.
If the target index is greater than p, recurse into the right piece only.
If the target index is smaller than p, recurse into the left piece only.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Partition, then recurse into only the side holding the answer

Statusstart

Partition the whole array around pivot 4 (last element).

What happens in this step

array: [3, 2, 1, 5, 6, 4], k = 2 → target index = length - k = 6 - 2 = 4
pivot = arr[5] = 4 (last element)

Looking for whichever element ends up at index 4 once partitioned — that value is the 2nd largest.

Step 1 of 4

5. Solution

Solution

solution.tsTypeScript

function findKthLargest(nums, k) {
  const target = nums.length - k;

  function partition(arr, lo, hi) {
    const randomIndex = lo + Math.floor(Math.random() * (hi - lo + 1));
    [arr[randomIndex], arr[hi]] = [arr[hi], arr[randomIndex]];

    const pivot = arr[hi];
    let i = lo;

    for (let j = lo; j < hi; j++) {
      if (arr[j] < pivot) {
        [arr[i], arr[j]] = [arr[j], arr[i]];
        i++;
      }
    }

    [arr[i], arr[hi]] = [arr[hi], arr[i]];
    return i;
  }

  function quickSelect(arr, lo, hi) {
    if (lo === hi) return arr[lo];

    const p = partition(arr, lo, hi);
    if (p === target) return arr[p];
    if (p < target) return quickSelect(arr, p + 1, hi);
    return quickSelect(arr, lo, p - 1);
  }

  return quickSelect(nums, 0, nums.length - 1);
}

Time: O(n) average, O(n²) worst case
Space: O(log n) average for the recursion stack

6. Test cases

Test cases

Input	Expected	Covers
`nums = [3, 2, 1, 5, 6, 4], k = 2`	`5`	example from the docstring
`nums = [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4`	`4`	duplicate values across the array
`nums = [1], k = 1`	`1`	smallest valid input, a single element
`nums = [7, 10, 4, 3, 20, 15], k = 3`	`10`	k in the middle of the array
`nums = [2, 2, 2, 2], k = 2`	`2`	every value identical
`nums = [-1, -2, -3, -4], k = 1`	`-1`	negative values, k = 1 asks for the maximum
`nums = [5, 3, 8, 1], k = 4`	`1`	k equal to the array length asks for the minimum

Kth Largest Element in an Array