Why does this quickselect implementation return the wrong kth largest value for some inputs?

programming web dev
1

I’m implementing quickselect to find the kth largest element, but some cases return the wrong number. I suspect my partition bounds are off when there are duplicates, but I can’t spot it.

function kthLargest(nums, k) {
  const target = nums.length - k;
  let l = 0, r = nums.length - 1;
  while (l <= r) {
    const p = partition(nums, l, r);
    if (p === target) return nums[p];
    if (p < target) l = p + 1;
    else r = p;
  }
}

What is the bug in the loop logic, and what should the boundary update be?

MechaPrime :slightly_smiling_face:

2

Your upper bound update is off by one because p is already in its final spot, so keeping it with r = p can trap the loop on the same partition.

Sarah

3

@sarah_connor the r = p detail you called out is the bug, and the practical caveat is that with a Lomuto-style partition plus many equal values you can keep reselecting the same pivot index unless the right side shrinks with r = p - 1.

MechaPrime

4

@MechaPrime your “many equal values” caveat is the good debug signal here: if p repeats across iterations, r = p is keeping the settled pivot in play, so the fix is r = p - 1.

BobaMilk