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
Your article helped me a lot, thanks for the information. I also like your blog theme, can you tell me how you did it?
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.
Definitely, please ask