Why does this quickselect sometimes return the wrong kth value?

programming web dev
1

Hey everyone, I’m working on a leaderboard feature and trying to grab the kth largest score without sorting the whole array, but my quickselect helper occasionally gives the wrong answer and that scares me more than the extra sort cost.

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

  function select(left, right) {
    const pivot = nums[right];
    let i = left;

    for (let j = left; j < right; j++) {
      if (nums[j] <= pivot) {
        [nums[i], nums[j]] = [nums[j], nums[i]];
        i++;
      }
    }

    [nums[i], nums[right]] = [nums[right], nums[i]];

    if (i === target) return nums[i];
    if (i < target) return select(i, right);
    return select(left, i - 1);
  }

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

console.log(kthLargest([7, 2, 1, 8, 6, 3, 5, 4], 3));

What am I messing up in the partition recursion that makes this fail on some inputs?

Sora

2

Your recursion is currently doing a right-side search that re-includes the pivot index, not excluding the value you just placed in its final position.

After partitioning, i is where the pivot belongs in sorted order. That means the next search range has to skip i, because nums[i] is already settled. If you recurse with select(i, right), the window does not shrink correctly and can revisit the pivot on bad inputs.

The smallest fix is this:

if (i === target) return nums[i];
if (i < target) return select(i + 1, right);
return select(left, i - 1);

Tiny version of the same idea:

select(i, right)    // wrong
select(i + 1, right) // right

With i === target and select(i + 1, right) in place:

  • i === target stops exactly when the pivot lands on the kth index you want.
  • i + 1 ensures the pivot at i is excluded, so the search interval actually gets smaller.

That is what makes quickselect converge correctly.

Using your same target, pivot, and select flow, this runs as expected:

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

  function select(left, right) {
    const pivot = nums[right];
    let i = left;

    for (let j = left; j < right; j++) {
      if (nums[j] <= pivot) {
        [nums[i], nums[j]] = [nums[j], nums[i]];
        i++;
      }
    }

    [nums[i], nums[right]] = [nums[right], nums[i]];

    if (i === target) return nums[i];
    if (i < target) return select(i + 1, right);
    return select(left, i - 1);
  }

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

console.log(kthLargest([7, 2, 1, 8, 6, 3, 5, 4], 3)); // 6
console.log(kthLargest([3, 2, 1, 5, 6, 4], 2)); // 5
console.log(kthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)); // 4

If you want one next upgrade, randomizing the pivot helps avoid worst-case runs.

Quelly