Kth Largest Element in an Array – Leetcode Solution

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 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

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.

Leave a Comment

Your email address will not be published.