Kth Largest Element in an Array LeetCode Solution

Table of Contents

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 <= k <= nums.length <= 104
-104 <= nums[i] <= 104

Link: https://leetcode.com/problems/kth-largest-element-in-an-array/

Solution
#

I have stored all the elements in the array in a MaxHeap. Now if we do k-1 times extractMax() or poll() in Priority Queue, we will be left with the kth largest element at the top of the heap.

Time complexity: \(O(log N)\)

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

class Solution {
    /**
    * Stored the elements in a max heap
    * if we do extractMax() k-1 times
    * then we will be left with kth largest element
    * TC: O(k + logN)
    * SC: O(N)
    */
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
        maxHeap.addAll(Arrays.stream(nums).boxed().collect(Collectors.toList()));

        for(int i=0; i<k-1; i++) {
            maxHeap.poll();
        }

        return maxHeap.peek();
    }
}

Solution #

Solution
#