Find k Smallest Numbers from a million numbers

Problem

Given an array of n numbers (possibly very large, e.g., a million elements), find the k smallest numbers in the array. Return them in any order.

Examples

Example 1

Input: arr = [7, 10, 4, 3, 20, 15], k = 3
Output: [3, 4, 7]
Explanation: The three smallest numbers are 3, 4, and 7.

Example 2

Input: arr = [1, 23, 12, 9, 30, 2, 50], k = 4
Output: [1, 2, 9, 12]
Explanation: The four smallest numbers are 1, 2, 9, and 12.

Solution

Method 1 – Sorting

Intuition

Sort the array and return the first k elements. Simple but not optimal for very large arrays.

Approach

• Sort the array in ascending order.
• Return the first k elements.

Complexity

• ⏰ Time complexity: O(n log n), due to sorting.
• 🧺 Space complexity: O(1) (in-place sort).

Method 2 – Max Heap (Optimal for Large n, Small k)

Intuition

Maintain a max heap of size k. Iterate through the array, keeping only the k smallest elements seen so far.

Approach

• Build a max heap with the first k elements.
• For each remaining element, if it is smaller than the heap's maximum, replace the maximum and re-heapify.
• At the end, the heap contains the k smallest elements.

Code

C++

class Solution {
public:
    vector<int> kSmallest(vector<int>& arr, int k) {
        priority_queue<int> maxHeap;
        for (int i = 0; i < arr.size(); ++i) {
            if (maxHeap.size() < k) maxHeap.push(arr[i]);
            else if (arr[i] < maxHeap.top()) {
                maxHeap.pop();
                maxHeap.push(arr[i]);
            }
        }
        vector<int> ans;
        while (!maxHeap.empty()) {
            ans.push_back(maxHeap.top());
            maxHeap.pop();
        }
        return ans;
    }
};

Go

import "container/heap"

type IntHeap []int
func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] > h[j] } // max-heap
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

func KSmallest(arr []int, k int) []int {
    h := &IntHeap{}
    heap.Init(h)
    for _, v := range arr {
        if h.Len() < k {
            heap.Push(h, v)
        } else if v < (*h)[0] {
            heap.Pop(h)
            heap.Push(h, v)
        }
    }
    ans := make([]int, h.Len())
    for i := range ans {
        ans[i] = heap.Pop(h).(int)
    }
    return ans
}

Java

class Solution {
    public int[] kSmallest(int[] arr, int k) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        for (int num : arr) {
            if (maxHeap.size() < k) maxHeap.offer(num);
            else if (num < maxHeap.peek()) {
                maxHeap.poll();
                maxHeap.offer(num);
            }
        }
        int[] ans = new int[maxHeap.size()];
        int i = 0;
        while (!maxHeap.isEmpty()) ans[i++] = maxHeap.poll();
        return ans;
    }
}

Python

import heapq
class Solution:
    def k_smallest(self, arr: list[int], k: int) -> list[int]:
        if k == 0: return []
        heap = [-x for x in arr[:k]]
        heapq.heapify(heap)
        for x in arr[k:]:
            if -heap[0] > x:
                heapq.heappop(heap)
                heapq.heappush(heap, -x)
        return sorted([-x for x in heap])

Complexity

• ⏰ Time complexity: O(n log k), as each insertion/removal in the heap of size k is O(log k).
• 🧺 Space complexity: O(k), for the heap.

Method 3 – Quickselect (Hoare's Algorithm)

Intuition

Quickselect partitions the array so that the k smallest elements are in the first k positions (not necessarily sorted). Efficient for average case.

Approach

• Use the partitioning logic of quicksort to recursively find the kth smallest element.
• After partitioning, the first k elements are the k smallest.

Complexity

• ⏰ Time complexity: O(n) average, O(n^2) worst case.
• 🧺 Space complexity: O(1) (in-place).