Why can't two algorithms with the same time complexity pass the Kth Largest Element problem on LeetCode?

Question

I am trying to solve the "Kth Largest Element in an Array" problem on LeetCode. I have two different approaches that both theoretically have the same time complexity (O(n) on average), but only one of them passes the test cases while the other one times out. Here are the two approaches I have tried:

Approach 1: Quickselect (accepted)

int quickselect(int* nums, int l, int r, int k) {
    if (l == r)
        return nums[k];
    int partition = nums[l], i = l - 1, j = r + 1;
    while (i < j) {
        do i++; while (nums[i] < partition);
        do j--; while (nums[j] > partition);
        if (i < j) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    }
    if (k <= j) return quickselect(nums, l, j, k);
    else return quickselect(nums, j + 1, r, k);
}

int findKthLargest(int* nums, int numsSize, int k) {
    return quickselect(nums, 0, numsSize - 1, numsSize - k);
}

Approach 2: modified Quick Sort (time-out)

void q(int nums[], int left, int right, int k) {
    if (left >= right) return;

    int piv = nums[left];  // Select the first element as the pivot
    int l = left, r = right;

    while (l < r) {
        // From right to left, find the first element less than the pivot
        while (l < r && nums[r] <= piv) r--;
        nums[l] = nums[r];

        // From left to right, find the first element greater than the pivot
        while (l < r && nums[l] >= piv) l++;
        nums[r] = nums[l];
    }

    nums[l] = piv;  // Place the pivot in the correct position

    if (l == k) return;  // Found the kth element
    if (l < k) q(nums, l + 1, right, k);  // Search the right side
    else q(nums, left, l - 1, k);  // Search the left side
}

int findKthLargest(int* nums, int numsSize, int k) {
    q(nums, 0, numsSize - 1, k - 1);  // We use k - 1 because the array is 0-indexed
    return nums[k - 1];  // Return the kth largest element
}

Problem:
Time Complexity: Both algorithms should have an average time complexity of O(n).
Why it works for Approach 1: The first approach, which is a standard quickselect implementation, passes the test cases successfully on LeetCode.

Why it doesn't work for Approach 2: The second approach, despite having the same time complexity, is timing out for large test cases.

Quicksort/quickselect is notorious for being finicky with non-unique values (in particular single-pivot quicksort). Try terminating q()'s inner loops on nums[r(l)] < piv. (Find out how this makes a difference with repeated values.) — greybeard
– greybeard, Commented Mar 10 at 9:35

rcgldr · Accepted Answer · 2025-03-10 23:08:06Z

2

The second approach is not as fast as the first approach, as the inner loops involve two conditions to check for (l < r and (element <= pivot or element >=pivot)). I didn't check it to see if it ever fails.

The first approach is a variation of Hoare partition scheme, which eliminates the need for a bounds check to avoid scanning beyond either end of a partition, so that each inner loop only has one condition to test for (element < pivot or element > pivot). If the pivot or elements equal to pivot stops one or both of the inner loops, the following swap of that element prevents the next iteration of inner loops from going past the end of a sub-array.

edited Mar 10 at 23:08

answered Mar 10 at 23:02

rcgldr

29.4k3 gold badges41 silver badges70 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

greybeard Mar 10 at 23:43

(With partition = nums[l]/piv = nums[left], I can see how j/r does not have to be checked to be in range. Can you point out why this could be dispensable for i/l? (I do see the "If [something] stops": what if nothing does?) (The loop/assignment/loop/assignment partition variant too was published by Hoare in the early 60ies.))

greybeard Mar 11 at 6:13

(Thanks for spelling this out once more - serves me right for fumbling in including "the q() case" in my above question on top of not reading the last sentence successfully; I don't see r not needing the check.) I guess I was hoping for the answer state that/spell out q() can be modified for single comparison inner loops by 1: stopping at the pivot value, 2: starting at the end with a sentinal waiting at the other end, 3: checking l < r between the inner loops, too. (The question does 2.)

rcgldr Mar 11 at 6:16

@greybeard - I should have explained this better. In the first algorithm, both inner loops break if element == pivot. The first inner loop that increments i treats an element == pivot the same as an element > pivot, out of order. The second inner loop that decrements j treats an element == pivot the same as element < pivot., also out of order. Since elements == pivot are always considered out of order and then swapped, this prevents the next iteration of the inner loops from going out of range. Elements == pivot are treated similar to sentinel values.

rcgldr Mar 11 at 6:17

@greybeard - In the first algorithm, the last element can't be used for pivot, since than can lead to infinite recursion for quicksort(a, lo, j), when lo = 0 and j = 1. Using the middle element is best case if data is already sorted or reverse sorted, while using first element is worst case in the same situation.

Collectives™ on Stack Overflow

Why can't two algorithms with the same time complexity pass the Kth Largest Element problem on LeetCode?

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related