The problem requires us to find the kth largest element in an unsorted array without sorting the entire array. This implies that a more efficient algorithm than full sorting (O(n log n)) is desired.

The QuickSelect algorithm, a variation of QuickSort, provides an efficient solution with an average time complexity of O(n). It leverages the partitioning logic of QuickSort but only recurses into the partition that contains the kth largest element.

Intuition:

Imagine you're trying to find the median value in a collection of numbers. You don't necessarily need to sort the whole collection; you just need to strategically partition it until you isolate the median. QuickSelect does precisely this, adapting the partitioning strategy of QuickSort.

The core idea is to pick a 'pivot' element and partition the array around it. Elements smaller than the pivot go to the left, and larger elements go to the right. By comparing the pivot's position to k, we can determine which subarray to focus on for finding the kth largest element.

Step-by-step thinking:

Convert k to find the kth smallest element: Since QuickSelect naturally finds the kth smallest element, we convert the problem to finding the (n - k)th smallest element, where n is the length of the array.
Implement the quickSelect function: This function takes the array and the left and right indices of the portion to process as input.
Choose a pivot: Here, the rightmost element is chosen as the pivot. Other strategies could be used as well, such as random pivot selection to reduce the chance of worst case performance.
Partition the array: Iterate from the left index to the right index (excluding the pivot). If an element is less than or equal to the pivot, swap it with the element at index p and increment p. The variable `p` tracks the index where the next smaller element should be placed.
Place the pivot: After the loop, swap the pivot element (originally at the right index) with the element at index p. Now, all elements to the left of p are less than or equal to the pivot, and all elements to the right are greater than the pivot.
Check pivot position: If p is greater than k, the kth smallest element is in the left partition, so recurse on the left partition. If p is less than k, the kth smallest element is in the right partition, so recurse on the right partition. If p equals k, the pivot element is the kth smallest element, so return it.
Call quickSelect: Initialize the quickSelect function with the entire array and the target index k.
Return the result: The function will eventually return the kth largest element.

Time Complexity: O(n) average, O(n^2) worst case
Space Complexity: O(1) in-place, O(log n) call stack in average case, O(n) worst case

Learn Complexity

50. Kth Largest Element

Understand Before Coding

Visualize This Problem

Draw Your Approach

Example 1:

Example 2:

Constraints:

Learn

Topics

Companies

Hint

Use Cases