Given an array of integers, find the kth largest element in the array.
For example,
Given the input [3,2,1,5,6,4] and k = 2
The output is 5
Try out the solution here:
https://leetcode.com/problems/kth-largest-element-in-an-array/
Solution:
We can solve this problem in multiple ways.
Let’s look at three approaches.
Approach 1 – Sort the array
In this approach you just sort the array and return the n-k th element (n is the size of the array) which is the kth largest element from the end.
Here is the code:
class Solution {
public int findKthLargest(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length - k];
}
}
The time complexity is O(nlogn) because of the sorting.
There is no extra space used.
Approach 2 – Use max heap of size k
In this approach you can keep adding the elements to a max heap and if the size exceeds k pop out the top element.
This way the top element will always be the kth largest element.
Here is the code:
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> maxheap = new PriorityQueue<Integer>((n1,n2) -> n1-n2);
for(int i:nums){
maxheap.add(i);
if(maxheap.size() > k){
maxheap.poll();
}
}
return maxheap.poll();
}
}
Time complexity is O(nlogk) where log k is the time taken for any heap operation of size k.
Space complexity is O(k) which is the size of the heap
Approach 3 – Use Quick Select
This approach has better time complexity than the other approaches.
In this approach ,
We randomly choose an element from the array.
This is the pivot element.
Then we push all the elements less than the pivot element to the left.
This way the array will contain:
Elements smaller than the pivot, the pivot and then the elements greater than the pivot.
Now if the index of the pivot is equal to (n-k) then we have got the output, we return the element at the index of the pivot.
If the value of (n-k) is less than the pivot then we need to search in the left part of the array.
So, continue the quick sort to the left.
If the value of (n-k) is greater than the pivot then we need to search in the right part of the array.
So, continue the quick sort to the right.
Partitioning is a major part of this algorithm.
Here is the code to do the partitioning:
public int partition(int start,int end){
int pivotIndex = start + new Random().nextInt(end - start);
int pivotElement = this.nums[pivotIndex];
int currentIndex = start;
swap(pivotIndex,end);
for(int i=start;i<=end;i++){
if(this.nums[i] < pivotElement){
swap(currentIndex,i);
currentIndex++;
}
}
swap(currentIndex,end);
return currentIndex;
}
First, we choose a random number within the start and the end range.
Then we choose this number as the index.
We find the element at this index.
We swap this element to the end first .
Then we iterate through each element within the start and end range and move all elements less than the pivot to the left.
Maintain a pointer to the current index while you do the above.
After the iteration swap the last element (where we stored the pivot) with the current index element (which is the current position of the pivot)
Now all elements left to the pivot are lesser than it.
And all elements to the right of the pivot are greater than it.
Return this index.
Here is the quick select algorithm:
public int quickselect(int start,int end){
if(start == end) return this.nums[start];
int partitionIndex = partition(start,end);
if(partitionIndex == this.outputIndex){
return this.nums[outputIndex];
}
if(outputIndex < partitionIndex){
return quickselect(start,partitionIndex -1);
}
return quickselect(partitionIndex+1,end);
}
If the start and end index are the same, then we have no more elements to sort so return it.
Else if the returned pivot index is equal to the kth largest index, then return it.
If the kth largest index is less than this pivot, then we need to search left, so do quick select in the left part of the array.
If the kth largest index is greater than this pivot, then we need to search right, so do quick select in the right part of the array.
Here is the entire code:
class Solution {
int[] nums;
int outputIndex;
public int findKthLargest(int[] nums, int k) {
this.nums = nums;
this.outputIndex = nums.length - k;
return quickselect(0,nums.length-1);
}
public int quickselect(int start,int end){
if(start == end) return this.nums[start];
int partitionIndex = partition(start,end);
if(partitionIndex == this.outputIndex){
return this.nums[outputIndex];
}
if(outputIndex < partitionIndex){
return quickselect(start,partitionIndex -1);
}
return quickselect(partitionIndex+1,end);
}
public void swap(int left,int right){
int t = this.nums[left];
this.nums[left] = this.nums[right];
this.nums[right] = t;
}
public int partition(int start,int end){
int pivotIndex = start + new Random().nextInt(end - start);
int pivotElement = this.nums[pivotIndex];
int currentIndex = start;
swap(pivotIndex,end);
for(int i=start;i<=end;i++){
if(this.nums[i] < pivotElement){
swap(currentIndex,i);
currentIndex++;
}
}
swap(currentIndex,end);
return currentIndex;
}
}
Time complexity:
Every time we choose a pivot, we iterate through all the elements less than the pivot and then do the same recursively either through the left part or the right part of the pivot .
We ignore the other part.
So, on an average we iterate through all the elements once so time complexity is O(n).
But consider the worst case :
The array is sorted and k = n where n is the size of the array.
And the pivot chosen is always the last element.
In this case you iterate through all the elements for every pivot (one less element in each iteration)
Let’s say pivot is 7.
Here are the array elements we iterate through at each iteration:
First iteration:
1 2 3 4 5 6 7 (we iterate through all 7 elements since all of the elements left to the pivot are less than the pivot)
Second iteration:
12 3 4 5 6 (we iterate through 6 elements)
Third iteration
1 2 3 4 5 (we iterate through 5 elements)
Fourth iteration:
1 2 3 4 (4 elements)
Fifth iteration :
1 2 3 (3 elements)
Sixth iteration:
1 2 (2 elements)
Seventh iteration:
1 – (1 element) which is the Output
So total elements processed is 7 + 6 + 5 + 4 + 3 + 2 + 1 which is almost O( 7 ^ 2) = O(n ^ 2)
But this would rarely be the case as the pivot element will be random and not always the last element.
Space complexity:
We don’t use any extra space, so space complexity is O(1)
We declare a global int array for easier processing, but this just refers to the original int array and no extra space is allocated.
Leave a Reply