Find Kth largest number in an array.

Given an array with n elements (not necessarily distinct) and a number k , find the k’th largest element.

Example Test Cases

Sample Test Case 1

Array: 5, 2, 3, 4, 10
K: 1
Expected Output: 10
Explanation: Since 10 is the 1st largest element

Sample Test Case 2

Array: 3, 1, 8, 8, 9
K: 4
Expected Output: 3
Explanation: The 4th largest element is 3 , since the top 3 largest elements are 9, 8, 8 respectively.

Solution

We can solve this problem in two ways:

1. Sort the array in descending order and return the element at k - 1 position. Since, we can sort the array in place we won’t be using any extra space making our space complexity O(1) . However sorting the array will take O(nlogn) time.
2. If the k is small compared to n , the first algorithm shown above can be optimized further by using a min heap of size k . This solution is explained below:

The basic idea of this solution is to maintain the top k elements of the array in a heap. The smallest element in the above heap will be the smallest element in the top k elements.

Initially, the min heap would be empty. Now, we will push the first k elements of the array into the heap. At the end of this, the element the top element of the heap will be the kth largest within the first k elements of the array.

Now while iterating through the remaining elements of the array, for every element that we iterate over if it is smaller than the current top element of the heap we ignore it. (since, our heap should contain only the top K elements, and the top element in the heap is the smallest of all elements in the heap). Otherwise, we pop the top element from the heap and insert the current array element into the heap.

At the end of this process, we will have the top k elements of the array in the heap, and the top element of the heap will be the smallest of the top k elements and will be the answer. Take a look at the below code implementation for this algorithm

Solution Implementation

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

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

int main() {
    vector vec = { 3, 1, 8, 8, 9 };
    int k = 4;
    cout << k << "th largest no is " << findKthLargest(vec, k) << "\n";
    return (0);
}

Time Complexity

Since the heap size will always be K, any insertion or deletion will cost O(logK) time. Since, we are deleting at most n - k times the total time complexity will be O(nlogK) - O(klogK) which is equal to O(nlogK) . Also, since we have created a heap with size K, it will take up O(k) extra space.