LeetCode //C - 215. Kth Largest Element in an Array

215. Kth Largest Element in an Array

Given an integer array nums and an integer k, return the $k^{th}$ largest element in the array.

Note that it is the $k^{th}$ largest element in the sorted order, not the $k^{th}$ distinct element.

Can you solve it without sorting?
 

Example 1:

Input: nums = [3,2,1,5,6,4], k = 2
Output: 5

Example 2:

Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4

Constraints:

• $1<=k<=nums.length<=10^5$
• $-10^4<=nums[i]<=10^4$

From: LeetCode
Link: 215. Kth Largest Element in an Array

---

Solution:

Ideas：

1. Partitioning: The array is partitioned around a randomly chosen ‘pivot’ element. Partitioning means rearranging the array so that:

• All elements greater than the pivot come before the pivot.
• All elements equal to the pivot come next.
• All elements less than the pivot come last.

2. Selection:

• If the pivot’s position is exactly k after partitioning, then the pivot is the k-th largest element, and we return it.
• If the pivot’s position is greater than k, we know that the k-th largest element must be to the left of the pivot, so we recursively select from the left subarray.
• If the pivot’s position is less than k, we select from the right subarray.

3. Three-Way Partitioning: The implementation uses a three-way partition to deal with duplicates efficiently. Instead of two partitions (less than and greater than the pivot), it creates three:

• Elements less than the pivot.
• Elements equal to the pivot.
• Elements greater than the pivot.

This is particularly efficient if there are many duplicates because it ensures that we only have to recurse on one of the partitions that actually contains the k-th largest element.

4. Iterative Approach: Instead of the standard recursive approach used in QuickSelect, this code uses an iterative loop, which can be more space-efficient (it uses less stack space) and might be slightly faster due to less overhead from function calls.

5. Random Pivot Selection: By randomly selecting a pivot each time we partition, we reduce the likelihood that we’ll encounter the worst-case performance of $O(n^2)$ time, which can happen if we consistently pick bad pivots (such as when the array is already sorted or contains many identical elements).

6. Random Seed Initialization: Before running QuickSelect, we initialize the random seed with srand(time(NULL)). This ensures that different runs of the program will use different seeds for the random number generator, which in turn makes it very likely that different pivot elements will be chosen in different runs.

Code:

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// This function partitions the array into three parts:
// - Elements greater than the pivot
// - Elements equal to the pivot
// - Elements less than the pivot
void partition(int* nums, int left, int right, int* lp, int* rp) {
    if (right - left <= 1) {
        if (nums[left] < nums[right])
            swap(&nums[left], &nums[right]);
        *lp = left;
        *rp = right;
        return;
    }

    int pivot = nums[right];
    int less = left; // Track start of less than pivot
    int great = right; // Track end of greater than pivot
    int i = left;
    while (i <= great) {
        if (nums[i] > pivot) {
            swap(&nums[i++], &nums[less++]);
        } else if (nums[i] < pivot) {
            swap(&nums[i], &nums[great--]);
        } else {
            i++;
        }
    }
    *lp = less; // Start of elements equal to pivot
    *rp = great; // End of elements equal to pivot
}

int quickSelect(int* nums, int left, int right, int k) {
    srand(time(NULL)); // Seed for randomness
    while (left <= right) {
        int lp, rp;
        partition(nums, left, right, &lp, &rp); // Perform the partitioning
        if (k >= lp && k <= rp) // If k is within the equal range, return the element
            return nums[k];
        else if (k < lp)
            right = lp - 1; // Discard right side
        else
            left = rp + 1; // Discard left side
    }
    return -1; // If the loop exits, the input was not valid
}

int findKthLargest(int* nums, int numsSize, int k) {
    return quickSelect(nums, 0, numsSize - 1, k - 1); // k - 1 because arrays are 0-indexed
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54