Posts Kth Largest Element in an Array
Post
Cancel

Kth Largest Element in an Array

This question is part of NeetCode150 series.

Problem Description

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. You must solve it in O(n) time complexity. leetcode

Solution

The trivial way is to sort the list and return the element at K-1 index.

We can also make use of Max Heap which is going to O(N + KlogN) time complexity.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    
    public int findKthLargest(int[] nums, int k) {
        
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Collections.reverseOrder());
        
        for(int i=0; i<nums.length; i++){
            pq.add(nums[i]);
        }
        
        int ans = 0;
        
        for(int i=1; i<k; i++){
            pq.poll();
        }
        
        return pq.poll();
        
    }
    
}
This post is licensed under CC BY 4.0 by the author.