Kth Largest Element in an Array | LeetCode 215

In this blog, we will solve LeetCode Coding Problem ” Kth Largest Element in an Array”. We solve this coding problem by using min heap.

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.

Can you solve it without sorting?

Constraints

• 1 <= k <= nums.length <= 105
• -104 <= nums[i] <= 104

Example

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

Output: 5

Solution

We will solve this coding problem by building heap of size k. Step by step breakdown of solution is as follows.

• We will iterate through nums array. For each element
  • we will push element to min heap.
  • If heap size is more than k, remove top element of heap.
• Return top of heap as function return value.

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> minHeap;

        for(int i=0; i<nums.size(); i++) {
            minHeap.push(nums[i]);

            if(minHeap.size() > k) {
                minHeap.pop();
            }
        }

        return minHeap.top();
    }
};

Time Complexity

O(nlogk) where n = number of elements in array.

Space Complexity

O(k) since we are building a k size min heap.

Thanks for reading and have a nice day.