Code Logo

Priority Queue Kth Largest

Published at25 Jul 2026
Created by
Priority Queue Easy 1 views
Like0

Given an array of integers and an integer k, find the kth largest element in the array. The kth largest is the element that would appear at position k-1 (0-indexed) if the array were sorted in descending order. Return the element itself. If k exceeds the array length, return -1.

For example, in the array [3, 2, 1, 5, 6, 4] with k=2, the sorted descending order is [6, 5, 4, 3, 2, 1], and the 2nd largest is 5. With k=1, the result is 6 (the maximum). With k=6, the result is 1 (the minimum). With k=7, which exceeds the array length, return -1.

The kth largest element is a classic selection problem with applications in statistics (percentiles), leaderboards (top performers), and ranking systems. It is the mirror image of the kth smallest problem and shares the same algorithmic approaches.

The simplest approach sorts the array in descending order and returns the element at index k-1. This runs in O(n log n) time. A more efficient approach for large arrays uses a min-heap (priority queue) of size k: maintain only the k largest elements seen, and the top of the heap (the smallest among them) is the kth largest.

Edge cases include k=1 (return the maximum element), k equal to the array length (return the minimum element), k larger than the array length (return -1), and an empty array (return -1).

Example Input & Output

Example 1
Input
[1],2
Output
-1
Explanation

Not enough elements

Example 2
Input
[10,5,7],1
Output
10
Explanation

1st largest is max

Example 3
Input
[3,1,4,1,5],2
Output
4
Explanation

2nd largest is 4

Example 4
Input
[5],1
Output
5
Explanation

Single

Example 5
Input
[1,2,3],3
Output
1
Explanation

3rd largest is min

Algorithm Flow

Recommendation Algorithm Flow for Priority Queue Kth Largest

Solution Approach

Maintain a min-heap of size k to track the k largest elements. For each element, push it into the heap. If the heap exceeds size k, pop the smallest element (the heap's top). After processing all elements, the heap contains the k largest values, and its top is the kth largest.

function kthLargest(arr, k) {
  if (k > arr.length || arr.length === 0) return -1;
  var heap = [];
  function push(v) { heap.push(v); heap.sort(function(a, b) { return a - b; }); }
  function pop() { return heap.shift(); }
  for (var i = 0; i < arr.length; i++) { push(arr[i]); if (heap.length > k) pop(); }
  return heap[0];
}

The heap only retains the k largest values, discarding smaller ones. The top element is the kth largest after the full pass.

Time O(n log k), Space O(k).

Best Answers

java
import java.util.*;
class Solution {
    public int solution(int[] nums, int k) {
        if(k>nums.length)return -1;int[] s=nums.clone();Arrays.sort(s);return s[s.length-k];
    }
}