Leetcode - Kth largest element in an array

 

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.

You must solve it in O(n) time complexity.

 

Example 1:

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

Example 2:

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

Solution

    This problem can be easily solved by simply sorting an array and then finding the nth position from last position because in a sorted array, biggest element would be the last and so on consecutively as we move on to lower positions. 

Implementation : 

int findKthLargest(vector<int> &nums, int k){

    // quick_sort(nums, 0, nums.size()-1);  -- Uncomment this to execute own implementation of sorting using quick sort
   // printVect(nums);

    sort(nums.begin(), nums.end());  // in built library sort function to sort.

    int biggest = 0;
    
    for(int i = nums.size()-1; i >= 0 ; i--){
        if(k!=0){
                biggest = nums[i];
                k--;
        }
            
    }

    return biggest;
} 

Now for the purpose of learning, I have also implemented a quick sort algorithm. I believe the purpose of this question or challenge is to familiarize yourself with a quick sort algorithm because finding the Kth position is not hard at all once an array is sorted. 

So, I would highly recommend you to learn about Quick sort algorithm too while you code for this problem. 

You can find the source code here of my own implementation - KthLargestElement.cpp.

Once again, hope you learn something new and happy coding.