Quick Select Algorithm
Quick Select is a variation of the quicksort algorithm. It is an optimized way to find the kth smallest/largest element in an unsorted array.
Algorithm:
- The partition part of the algorithm is same as that of quick sort.
- After the partition function arranges the elements in list according to the pivot and returns the pivot_index, instead of recursing both sides of the pivot index, we recurse only for the part that contains our desired element
Time Complexity Analysis:
Worst case: Worst case occurs when we pick the largest/smallest element as pivot.
Best case: Best case occurs when we partition the list into two halves and continue with only the half we are interested in.
The time complexity for the average case for quick select is O(n) (reduced from O(nlogn) — quick sort). The worst case time complexity is still O(n²) but by using a random pivot, the worst case can be avoided in most cases. So, on an average quick select provides a O(n) solution to find the kth largest/smallest element in an unsorted list.
Practice : Kth Largest Element in an Array [ LeetCode — 215]
Problem Link:
Problem Description:
Given an integer array nums and an integer k, return the kth largest element in the array.
Note that it is the kth largest element in the sorted order, not the kth distinct element.
Solution 1: Simple and Easy
Sort the given input list in reverse order and print the kth element. The time complexity is O(nlogn).
Solution 2: Using Max-Heap
Build a max-heap and extract the elements k times. The last extracted element will be the answer. The time complexity for building max-heap is O(n) and performing heapify operation is O(logn). So the overall complexity will be O(n+klogn).
The above solutions are decent enough and give you the desired answer. But in interviews, you are asked to solve the problem in O(n).
Solution 3: Quick Select
Quick select allows us to solve the problem in O(n) on an average. Using randomized pivot, we can avoid the worst case in most cases. Hence, when asked in interviews, quick select should be your answer as it gives a better time complexity solution.
