Kth Largest Element in an Array medium

Problem Statement

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

You can assume k is always valid, 1 ≤ k ≤ array's length.

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

Steps to Solve

We can solve this problem using several approaches:

1. Sorting: Sort the array in descending order and return the element at index k-1. This is simple but not very efficient.

2. Heap (Priority Queue): Use a min-heap of size k. Iterate through the array. If the current element is greater than the smallest element in the heap (heap's root), replace the root with the current element and heapify. After iterating through the array, the root of the heap will be the kth largest element. This is more efficient than sorting for large arrays.

3. Quickselect (Hoare's selection algorithm): This is an average linear time algorithm. It's based on the idea of QuickSort but only recursively processes one partition. We partition the array around a pivot, and if the pivot's index is k-1, we've found our element. If the pivot's index is less than k-1, we recurse on the right partition; otherwise, we recurse on the left. This approach is generally the most efficient.

Explanation of Quickselect

Quickselect operates similarly to quicksort. It selects a pivot, partitions the array around the pivot, and then recursively searches only within the partition that contains the kth largest element. This avoids unnecessary sorting of the entire array.

The key is choosing a good pivot. A poor pivot choice can lead to worst-case O(n²) time complexity, but with randomized pivot selection or a median-of-medians pivot selection, the average time complexity is O(n).

Code (C++) using Quickselect

#include <iostream>
#include <vector>
#include <algorithm> // Only for random_shuffle (optional)

using namespace std;

int partition(vector<int>& nums, int left, int right, int pivotIndex) {
    int pivotValue = nums[pivotIndex];
    swap(nums[pivotIndex], nums[right]); // Move pivot to end
    int storeIndex = left;
    for (int i = left; i < right; ++i) {
        if (nums[i] > pivotValue) { // Adjust comparison for kth largest
            swap(nums[storeIndex], nums[i]);
            storeIndex++;
        }
    }
    swap(nums[right], nums[storeIndex]); // Move pivot to its final place
    return storeIndex;
}


int quickselect(vector<int>& nums, int left, int right, int k) {
    if (left == right) return nums[left];

    // Randomize pivot for better average case performance
    random_shuffle(nums.begin() + left, nums.begin() + right + 1);

    int pivotIndex = left + (right - left) / 2;  //Choose a pivot
    pivotIndex = partition(nums, left, right, pivotIndex);

    if (pivotIndex == nums.size() - k) { //kth largest element index
        return nums[pivotIndex];
    } else if (pivotIndex > nums.size() - k) {
        return quickselect(nums, left, pivotIndex - 1, k);
    } else {
        return quickselect(nums, pivotIndex + 1, right, k);
    }
}


int findKthLargest(vector<int>& nums, int k) {
    return quickselect(nums, 0, nums.size() - 1, k);
}

int main() {
    vector<int> nums1 = {3, 2, 1, 5, 6, 4};
    cout << findKthLargest(nums1, 2) << endl; // Output: 5

    vector<int> nums2 = {3, 2, 3, 1, 2, 4, 5, 5, 6};
    cout << findKthLargest(nums2, 4) << endl; // Output: 4

    return 0;
}

Complexity

• Time Complexity: Average case O(n) for Quickselect. Worst-case O(n²) if pivot selection is consistently bad. Sorting would be O(n log n).
• Space Complexity: O(log n) in average case due to recursive calls (stack space for Quickselect). Sorting in-place algorithms have O(1) space complexity. The heap approach would use O(k) space for the heap.