LeetCode- 215. Kth Largest Element in an Array | C++ STL

Explanation and Code.

Problem Statement:

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.

Check out the Problem → Question
Full Code → Git

Example:

Input: nums = [3,2,1,5,6,4], k = 2
Output: 5

Approach:

First, let’s discuss how, in general, we can get the Kth MAX number in any Array.

Brute Force:

The most brute approach will be finding all max numbers and removing them from the array until we find the K th Max.

Ex- for 3rd largest
[10,20,50,30,90,40] — MAX 1-90 (remove)
[10,20,50,30,40] — MAX 2-50 (remove)
[10,20,30,40] — MAX 3-40 (remove)

Hence we find our 3rd Max that is 40.

Time Complexity :

For Searching Max each time it will be dependent on Array size.
For an Array of N Size.
Time taken will be for:
1st Iteration as N
2nd Iteration as N-1
and so on….

N+N-1+N-2……+1 = (N²+ N)/2

This gives us a Time Complexity of order (N²) which is not a very optimal solution.

Optimized Solution:

A good way to approach the problem will be using the Partitioning concept.

Partition Concept is used in Quick Sort, Where we Divide an Array-based on a pivot that we choose arbitrarily.

You can take a closer look at Quick Sort in this article.

Quick Sort Explained | C++ STL

In Brief, In Partition Technique we pick a pivot element, then move the pivot element to its correct position and partition the surrounding array. The idea is, not to do complete quicksort, but stop at the point where the pivot itself is k’th smallest element.

CODE :

class Solution {
public:
    inline int partition(vector<int>& nums,int low, int high,int k){
        
        int pivot = nums[high];
        int p = low; //index of the pivot
        for (int i= low; i<high; i++){
            if (nums[i] <= pivot){
                swap(nums[i],nums[p]);
                p++; 
       //a number is less than pivot, index of pivot increment by 1
            }
        }
        swap(nums[p],nums[high]);     
        //cout <<low << " " << high << " " <<p <<endl;
        if (k == p){
            return nums[p];
        }
        else if (k > p) { 
        //since all the numberis less pivot is in the left of the pivot, the result can only be in the range [high-k,high]
             return partition (nums, p+1,high,k);
        }
        else{
            return partition (nums, low,p-1,k);
        }
        
    }
    int findKthLargest(vector<int>& nums, int k) {
        k = nums.size()-k; //index
        return partition (nums,0,nums.size()-1,k);
    }
};

Competetive Code

There are many other ways to complete this in a few lines with advanced DS such as Maps and Sets.

With C++ you can use the sort function as well.

An implementation that can help to solve in a few lines:

with Sort():

int findKthLargest(vector<int>& nums, int k) {
        if(nums.size()==1)
            return nums[0];
        sort(nums.begin(),nums.end());
        return nums[nums.size()-k];
    }

Other than this you can use MinHeap, Priority Queue as well

int findKthLargest(vector<int>& nums, int k) 
    {     
        priority_queue<int,vector<int>,greater<int>> minheap;       
        for(int i=0;i<nums.size();i++)
        {
            minheap.push(nums[i]);            
            if(minheap.size()>k)  
                maxheap.pop();            
        }
        return minheap.top();        
    }

If you have any suggestions please feel free to connect with us or comment with your thoughts.

Happy Coding.