AlgoMaster Sheet – Kth Largest Element In An Array

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.

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

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

Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.   

Practice Questions   Kth Smallest Element in the Array

Solution 1: Sorting the Array

The most naive approach:

• To sort the given array in descending order.
• The index of kth Largest element = k-1 ( zero-based indexing ) 

• The array can also be sorted in ascending order.
• The index of kth Largest element = n-k 

Time Complexity: O(NlogN), where N is the size of the array.
Space Complexity: O(1), since no additional space is used.

#include <bits/stdc++.h>
using namespace std;

void findKthLargest(vector<int> &nums, int k)
{
    //sort the array
    sort(nums.begin(), nums.end());
    int n = nums.size();    //array size

    cout << "kth Largest element " << nums[n - k] <<endl;
}

int main()
{
    
    vector<int> nums = {3,2,1,5,6,4};

    findKthLargest(nums, 2);

    return 0;
}

Output:

kth Largest element 5

Solution 2: Using Heap

• Initialise a max-heap.
• Insert all the elements of the given array into the max heap.

• Since the top element of the max-heap is the largest element of the heap , we will remove the top K-1 elements from the heap .  The top element will be Kth Largest element.
• To get the Kth Smallest element , we will use a min-heap . After removal of top k-1 elements , the Kth Smallest element is top of the Priority queue.

Time Complexity: O(K + (N – K) * log(K) ), where N is size of the array.
Space Complexity: O(K), since the heap is used.

#include <bits/stdc++.h>
using namespace std;

int findKthLargest(vector<int> &nums, int k)
{
    priority_queue<int> basket;
    for (auto number : nums)
    {
        basket.push(number);
    }
    int resultant = 0;
    while (k--)
    {
        resultant = basket.top();
        basket.pop();
    }

    return resultant;
}

int main()
{

    vector<int> nums = {3, 2, 1, 5, 6, 4};

    cout << "kth Largest element: " << findKthLargest(nums, 2) << endl;
    
    return 0;
}

Output:

kth Largest element 5

To master AlgoMaster Sheet – Kth Largest Element In An Array in the most efficient and effective way, do check out this:

This article is contributed by : Sayan Dutta to this article on csforall.in