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.

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

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

3 Comments

  1. gate.io
    February 9, 2023

    Your article helped me a lot, thanks for the information. I also like your blog theme, can you tell me how you did it?

  2. gate io
    February 10, 2023

    Thank you, your article has benefited me a lot and helped me a lot. After reading carefully, I still have some doubts, would you like to help me solve it? I’ll be back often and follow up on this comment. thank you for your help.

Leave a Comment