Quickselect in TypeScript: Solving 'Kth Largest Element in an Array'

Kth Largest Element in an Array is one of those problems that looks more specialised than it really is. Strip the wording back, and the task is simply:

• find one position in the sorted order
• without necessarily sorting everything

That last part is what makes the problem interesting. If we only need the kth largest value, a full sort may be doing more work than the question actually asks for.

Three Sensible Answers Exist

This is not a one‑answer problem. There are three genuinely respectable approaches:

1. sort the whole array
2. keep a min‑heap of size k
3. use quickselect

The first is the easiest to write. The second is a great general‑purpose pattern. The third is the most algorithmically direct if we only need one order statistic.

The Easiest Answer: Full Sort

There is nothing wrong with this as a first pass:

export const findKthLargest = (values: number[], k: number): number => {  const sortedValues = [...values].sort((left, right) => right - left);  return sortedValues[k - 1];};

That is short, readable, and fine for many real applications.

The reason it is not the best answer here is simple:

• we do not need the entire array in order
• we only need one element's final position

The Heap Answer is Strong Too

A min‑heap of size k is another good route:

• keep only the current top k values
• if the heap grows beyond size k, remove the smallest
• the heap root finishes as the kth largest element

That is a very useful pattern, especially when:

• the input is streaming
• we want the top k items rather than just one selected rank

It is also closely related to the heap‑based Top K Frequent Elements article in the site's queue.

For this specific problem, though, quickselect is the sharper fit.

Why Quickselect is the Right Idea

Quickselect borrows the partitioning step from quicksort. We choose a pivot, partition the array around it, and then only continue on the side that still contains the target index.

That is the important difference from quicksort:

• quicksort recurses into both sides
• quickselect throws one side away immediately

If we only care about one final rank, that is exactly what we should want.

A Practical TypeScript Implementation

const swap = (values: number[], left: number, right: number): void => {  const temporary = values[left];  values[left] = values[right];  values[right] = temporary;};const partition = (  values: number[],  left: number,  right: number,  pivotIndex: number): number => {  const pivotValue = values[pivotIndex];  swap(values, pivotIndex, right);  let storeIndex = left;  for (let index = left; index < right; index += 1) {    if (values[index] < pivotValue) {      swap(values, storeIndex, index);      storeIndex += 1;    }  }  swap(values, storeIndex, right);  return storeIndex;};export const findKthLargest = (values: number[], k: number): number => {  const workingValues = [...values];  const targetIndex = workingValues.length - k;  let left = 0;  let right = workingValues.length - 1;  while (left <= right) {    const pivotIndex =      left + Math.floor(Math.random() * (right - left + 1));    const sortedPivotIndex = partition(      workingValues,      left,      right,      pivotIndex    );    if (sortedPivotIndex === targetIndex) {      return workingValues[sortedPivotIndex];    }    if (sortedPivotIndex < targetIndex) {      left = sortedPivotIndex + 1;    } else {      right = sortedPivotIndex - 1;    }  }  throw new Error('k is out of range');};

Why the target index is length ‑ k

Quickselect is easiest to reason about in ascending order.

If the array were fully sorted ascending, then:

• the largest item would be at index length ‑ 1
• the 2^nd largest would be at index length ‑ 2
• the kth largest would be at index length ‑ k

That is why the code converts the question into:

• find the element that belongs at targetIndex

What the Partition Step Guarantees

After partitioning around the pivot:

• everything left of the pivot's final index is smaller
• everything right of it is greater than or equal to it

The pivot is therefore in its final sorted position.

That is the crucial moment. Once we know the pivot's final position, there are only three possibilities:

• it is exactly the target index, so we are done
• it is too far left, so the answer must be on the right
• it is too far right, so the answer must be on the left

And because we only care about one target position, we throw the irrelevant side away immediately.

Why I Randomise the Pivot

Plain quickselect with a fixed pivot choice can degrade badly on unlucky inputs. Randomising the pivot helps avoid repeatedly making terrible partitions.

That does not change the theoretical worst case, but it makes the average behaviour much more trustworthy in practice.

This is one of those places where a small implementation detail makes the algorithm feel much less brittle.

Comparing the Three Approaches Properly

The full sort version is best when:

• simplicity matters most
• the input size is modest
• having the whole array sorted is acceptable work

The heap version is best when:

• we want a more predictable O(n log k) structure
• we might later generalise the code to "top k elements"
• the data may arrive incrementally

Quickselect is best when:

• we need one selected rank
• we do not care about fully sorting the rest
• average‑case linear time is the right trade‑off

So for this exact LeetCode problem, quickselect is the best algorithmic answer. In production application code, I would still happily choose full sort if the data size was small and clarity mattered more than squeezing out the extra asymptotic win.

Common Mistakes

Sorting Descending and Then Claiming That is the Only Serious Answer

It is a valid answer, not the only one.

Forgetting that the kth largest becomes length ‑ k in ascending‑index terms

That off‑by‑one conversion is the part to treat carefully.

Recursing into Both Partitions

That turns quickselect back into quicksort.

The Broader Lesson

This problem is useful because it asks a good question of our instincts:

• do we really need full order here?

Often the answer is no. Once we notice that, selection algorithms start to feel much more natural.

The Part Worth Keeping

• Full sort is simplest but does more work than the question requires.
• A heap is a strong general‑purpose alternative.
• Quickselect is the best fit when we only need one final rank and want to avoid sorting the entire array.

Kth Largest Element in an Array is a good reminder that order statistics are not the same problem as full ordering, even if they are close relatives.