The link to the problem: https://leetcode.com/problems/kth-largest-element-in-an-array/
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.
Example:
Input: [3,2,1,5,6,4] and k = 2
Output: 5Thoughts:
The easiest way to solve the problem is to sort the array then return the kth largest element in the array. However, that won’t be the best solution to this problem since we shouldn’t waste our time doing some extra work if we don’t have to. Time complexity will be O(nlogn) if we use merge sort or quicksort; will be even O(n²) if we use bubble sort or selection sort.
Then we need to think, is there any way we can find the kth element without needing to sort the whole array? Is there any algorithm that can help us to know the position of the current element?
If you know the idea of quicksort, you might think up with the idea of using the “partition” method provided in quicksort. It’s fine if you are not familiar with the idea, we will talk about how we use it in detail. Let’s see how it works and how we can use the partition method to solve this problem in O(n)!
Code Logic:
We want to create a partition method that will always return the correct position of the “pivot” while the array is also partitioned into 2 parts — the numbers that are less than the pivot and the numbers that are greater than the pivot. We usually let the last element of the given range of the array be the pivot. If you are not familiar with the partition method in quicksort at all, we will show the idea of how we partition the array later in the example.
First thing is that, in this problem, we are asked to find the kth largest element. Since in the partition method, we will always find the “correct position” (0-based array indexing) of a number, we will change the definition of k to “find the kth smallest number while the range of k is from 0 to (n-1)”. Since our array our 0-based, we will also consider the 0th smallest number as the smallest number.
In the main code, what we are going to do is calling the partition method and get the position. When we said the term “position”, it also represents the rank of the pivot. Hence, after we know the rank of the current number, we know where we can find the rank k number — if the rank is less than k, that means the kth element in the array is on the left of the current number; and vice versa.
Below is the code using the logic:
public int findKthLargest(int[] nums, int k) {
int n = nums.length;
return helper(nums, 0, n-1, n-k);
}
public int helper(int[] nums,int s,int e,int k){
int rank = partition(nums, s, e);
if(rank==k)
return nums[rank];
else if(rank<k)
return helper(nums, rank+1, e, k);
else
return helper(nums, s, rank-1, k);
}
public int partition(int[] nums, int s, int e){
int pivot = nums[e];
int i = s-1;
for(int j=s;j<e;j++)
{
if(nums[j]>pivot)
continue;
swap(nums,++i,j);
}
swap(nums,i+1,e);
return i+1;
}
public void swap(int[] nums,int i,int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}Example of the partition method:
We will always make the last element in the given array range [s, e] as our pivot. What we are going to do is keep swapping the elements when some condition is met. Our goal is to find the correct position/rank of the pivot and also partition the array at the same time. We will always swap the numbers that are less than the pivot to the front of the array. It is not guaranteed that the whole array will be sorted but we are only sure that we place the pivot at the correct position.
There are 4 important variables in this method:
- s: the starting position of the array
- e: the ending position of the array
- j: the index that will traverse from s to e
- i: the index that always points to the “most recent visited element” that is less than the pivot. The default value is s-1, which represents currently there are no numbers that are less than the pivot. After we traversed the designated range of the array, (i+1) will be the correct position for the pivot.
👷For example, if we have an array like [2,5,9,1,7,3] and s = 0, e = 5
🔧Step 0. Initial State, i = -1, j = 0
🔧Step 1. j = 0: We are going to compare the numbers that j points to with the pivot. Since arr[0] is less than the pivot, we swap the numbers of arr[i+1] and arr[j] and move i forward. Currently, arr[i+1] and arr[j] points to the same element, so we can’t really tell any difference in the array.
⚠️The reason why we swap arr[i+1] and arr[j] but not arr[i] and arr[j] — Since we always assume i points to the most recent visited element that is less than the pivot, that means arr[i] currently is less than the pivot and we don’t want to push it away. Hence, we will swap arr[j] (≤pivot) with arr[i+1] (>pivot) so that the small number will be moved forward.
🔧Step 2. j = 1: We are going to compare the numbers that j points to with the pivot. Since arr[1] is greater than the pivot, we will do nothing.
🔧Step 3. j = 2: We are going to compare the numbers that j points to with the pivot. Since arr[2] is greater than the pivot, we will do nothing.
🔧Step 4. j = 3: We are going to compare the numbers that j points to with the pivot. Since arr[3] is less than the pivot, we swap the numbers of arr[i+1] and arr[j] and move i forward. Hence, we will swap arr[1] and arr[3].
🔧Step 5. j = 4: We are going to compare the numbers that j points to with the pivot. Since arr[4] is greater than the pivot, we will do nothing.
🚧And j reaches the end, but wait, there’s one more important thing we need to do. Currently, we know that all the positions from s to i contains all the numbers that are less than the pivot. Hence, the correct position for our pivot is the position RIGHT AFTER i. Our final step — swap arr[i+1] and arr[e] (i.e., where our pivot is):
We can see from the above graph that although the array is not sorted, the position of our original pivot is placed in the correct position.
