Kth Smallest Element

Problem Statement

Given an unsorted array of integers nums and an integer k, return the K-th smallest element.

Input

An integer array nums and an integer k with 1 ≤ k ≤ nums.length.

nums = [7, 10, 4, 3, 20, 15]
k    = 3

Output

The K-th smallest value — a single integer.

7
 
// sorted asc: [3, 4, 7, 10, 15, 20]
// 3rd smallest → 7

Constraints

• 1 ≤ k ≤ nums.length ≤ 10⁵
• -10⁴ ≤ nums[i] ≤ 10⁴

Intuition

Symmetric to “Kth Largest”. Maintain a max-heap of size K. The root is the largest of the K smallest-so-far. When a new number arrives smaller than the root, evict the root. The final root is the K-th smallest. In Python, simulate a max-heap by negating the values.

step  x    heap (asc)       max-root   note
 1    7    [7]              7          push
 2    10   [7,10]           10         push
 3    4    [4,7,10]         10         push (size == k)
 4    3    [3,4,7]          7          push then pop → 10 evicted
 5    20   [3,4,7]          7          push then pop → 20 evicted
 6    15   [3,4,7]          7          push then pop → 15 evicted
                              ^root = 7 = 3rd smallest ✓

Solution

import heapq
 
def findKthSmallest(nums: list[int], k: int) -> int:
    max_heap: list[int] = []                 # store negatives → max-heap
    for num in nums:
        heapq.heappush(max_heap, -num)
        if len(max_heap) > k:
            heapq.heappop(max_heap)          # evict the largest
    return -max_heap[0]                      # un-negate

function findKthSmallest(nums: number[], k: number): number {
  const h = maxHeap<number>();
  for (const num of nums) {
    h.push(num);
    if (h.size > k) h.pop();                 // evict the largest
  }
  return h.peek()!;                           // root == k-th smallest
}

Complexity

Edge Case Thinking