In this post, we are going to solve the 215. Kth Largest Element in an Array problem of Leetcode. This problem 215. Kth Largest Element in an Array is a Leetcode medium level problem. Let’s see the code, 215. Kth Largest Element in an Array – Leetcode Solution.

Problem

Given an integer array nums and an integer k, return the k^th largest element in the array.

Note that it is the k^th largest element in the sorted order, not the k^th 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

Constraints

• 1 <= arr.length <= 104
• -104 <= arr[i], x <= 104

Now, let’s see the leetcode solution of 215. Kth Largest Element in an Array.

Kth Largest Element in an Array – Leetcode Solution

We are going to solve the problem using Priority Queue or Heap Data structure ( Max Heap ). Let’s see the solution.

215. Kth Largest Element in an Array – Solution in Java

class Solution {
    public static int findKthLargest(int[] nums, int k) {
        int ans = Integer.MAX_VALUE;
        PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
        for(int i=0;i<nums.length;i++){
                
            minHeap.add(nums[i]);
            if(minHeap.size() > k){
                minHeap.remove();
            }
        
        }
        while(minHeap.size() != 0){
            if(minHeap.peek() < ans){
                ans = minHeap.peek();
            }
             minHeap.remove();
        }
        return ans;
    }
}

215. Kth Largest Element in an Array – Solution in C++

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

215. Kth Largest Element in an Array – Solution in Python

def findKthLargest1(self, nums, k):
    heap = nums[:k]
    heapq.heapify(heap)  # create a min-heap whose size is k 
    for num in nums[k:]:
        if num > heap[0]:
           heapq.heapreplace(heap, num)
        # or use:
        # heapq.heappushpop(heap, num)
    return heap[0]

Note: This problem 215. Kth Largest Element in an Array is generated by Leetcode but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.