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

The same heap pattern also helps with the related Top K Frequent Elements problem, where frequency rather than numeric value determines which items we retain.

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

Why Quickselect is the Right Idea

Quickselect borrows partitioning from quicksort. Here we divide the current range into values below, equal to and above the pivot, then continue only in the range that 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, number] => {
  const pivotValue = values[pivotIndex];
  let smaller = left;
  let current = left;
  let greater = right;

  while (current <= greater) {
    if (values[current] < pivotValue) {
      swap(values, smaller, current);
      smaller += 1;
      current += 1;
    } else if (values[current] > pivotValue) {
      swap(values, current, greater);
      greater -= 1;
    } else {
      current += 1;
    }
  }

  return [smaller, greater];
};

export const findKthLargest = (values: number[], k: number): number => {
  if (!Number.isInteger(k) || k < 1 || k > values.length) {
    throw new Error('k is out of range');
  }

  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 [equalStart, equalEnd] = partition(
      workingValues, left, right, pivotIndex,
    );

    if (targetIndex < equalStart) {
      right = equalStart - 1;
    } else if (targetIndex > equalEnd) {
      left = equalEnd + 1;
    } else {
      return workingValues[targetIndex];
    }
  }

  throw new Error('No value found');
};

console.log(findKthLargest([7, 7, 7, 7], 2));  // 7

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:

• Values before the equal range are smaller than the pivot.
• Values within the equal range match the pivot.
• Values after the equal range are larger than the pivot.

The equal values occupy the positions they would fill in sorted order. We do not need to distinguish individual copies of the same value.

That gives us three possibilities for targetIndex:

• It falls inside the equal range, so the pivot value is the answer.
• It is before that range, so we continue on the left.
• It is after that range, so we continue on the right.

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

Why I Randomise the Pivot

Randomising the pivot helps avoid repeatedly poor splits of distinct values. The three‑way partition handles duplicates separately: all values equal to the pivot are grouped and skipped together.

For example, findKthLargest([7, 7, 7, 7], 2) returns 7 after one partition pass. A two‑way partition that moves only smaller values can repeatedly remove just one equal value, even with a random pivot. Three‑way partitioning avoids that duplicate‑heavy case; randomised quickselect still has a theoretical quadratic worst case on other unlucky partitions.

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.