Code Logo

Priority Queue Kth Smallest

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

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

For example, in the array [7, 10, 4, 3, 20, 15] with k=3, the sorted array is [3, 4, 7, 10, 15, 20], and the 3rd smallest element is 7. With k=1, the result is 3 (the minimum). With k=6, the result is 20 (the maximum). With k=7, which exceeds the array length, return -1.

This is a fundamental selection problem that appears in data analysis (finding percentiles), database query optimization, and competitive programming. The concept of the kth smallest element is closely related to order statistics, and finding it efficiently is important when you cannot afford to sort the entire dataset.

The most straightforward approach sorts the array in ascending order and returns the element at index k-1. This runs in O(n log n) time. For a large array where k is much smaller than n, a more efficient approach uses a max-heap (priority queue) of size k: maintain only the k smallest elements seen so far, and the top of the heap is the kth smallest.

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

Example Input & Output

Example 1
Input
[5],1
Output
5
Explanation

Single

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

3rd smallest is max

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

1st smallest is min

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

Not enough

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

2nd smallest is 1

Algorithm Flow

Recommendation Algorithm Flow for Priority Queue Kth Smallest

Solution Approach

Find the k-th smallest element in an array using a max-heap (priority queue) of size k. Maintain a heap of the k smallest elements seen so far. For each element, push it into the heap. If the heap size exceeds k, pop the largest element. After processing all elements, the heap's top is the k-th smallest.

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

This approach keeps only k elements in memory. After processing all n elements, the heap contains the k smallest values, with the largest of them (the k-th smallest) at the top.

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[k-1];
    }
}