kth largest element in an array

Problem Statement: Kth Largest Element

kth largest element in an array : Given an array and a number k where k is smaller than the size of the array, we need to find the k'th largest element in the given array. It is given that all array elements are distinct.

arr[] = [3,2,1,5,6,4]

k = 2

output: 5

We have presented two approaches to find the two elements:

Naive Approach

A simple solution is to sort(reverse) the given array using a O(N log N) sorting algorithm like Merge Sort, Heap Sort, etc, and return the element at index k-1 in the sorted array.

Approach 2: Efficient QuickSelect

This can be considered an optimised solution for this problem. In this, we pick the QuickSort for sorting. Analyzing the problem statement, we realize that we don't actually need to sort the entire array - we only need to rearrange its contents so that the kth element of the array is the kth largest or smallest.

Let's look at the basic ideas of the QuickSelect algorithm:

1. Pick a pivot element and partition the array accordingly

2. Pick the rightmost element as pivot

3. Reshuffle the array such that pivot element is placed at its rightful place - all elements less than the pivot would be at lower indexes, and elements greater than the pivot would be placed at higher indexes than the pivot

4. If pivot is placed at the kth element in the array, exit the process, as pivot is the kth largest element

5. If pivot position is greater than k, then continue the process with the left subarray, otherwise, recur the process with right subarray

int findKthLargest(vector<int>& nums, int k) {
	//partition rule: >=pivot   pivot   <=pivot
	int left=0,right=nums.size()-1,idx=0;
	while(1){
		idx = partition(nums,left,right);
		if(idx==k-1) break;
		else if(idx < k-1) left=idx+1;
		else right= idx-1;
	}
	return nums[idx];
}
int partition(vector<int>& nums,int left,int right){//hoare partition
	int pivot = nums[left], l=left+1, r = right;
	while(l<=r){
		if(nums[l]<pivot && nums[r]>pivot) swap(nums[l++],nums[r--]);
		if(nums[l]>=pivot) ++l;
		if(nums[r]<=pivot) --r;
	}
	swap(nums[left], nums[r]);
	return r;
}

class Solution:
    def findKthLargest(self, nums, k):
        def quickselect(nums, low, high, k):
            pos = partition(nums, low, high)
            if pos == k - 1:
                return nums[pos]
            elif pos >= k:
                return quickselect(nums, low, pos - 1, k)
            return quickselect(nums, pos + 1, high, k)
        def partition(nums, low, high):
            pivot = nums[high]
            i = low
            for j in range(low, high):
                if nums[j] > pivot:
                    nums[j], nums[i] = nums[i], nums[j]
                    i += 1
            nums[high], nums[i] = nums[i], nums[high]
            return i
                 
        return quickselect(nums, 0, len(nums) - 1, k)
ob1 = Solution()
print(ob1.findKthLargest([1,4,2,3,6,9], 3))

Time Complexity: O(n), in worst case it will be O(n²)

Space Complexity: O(1)

💡 Follow up: You can also do it by using heap data structure. Try it out!