Kth Smallest Element in an Unsorted Array: 4 C++ Approaches

Finding the Kth smallest element in an unsorted array does not require sorting the full array: the partition step borrowed from QuickSort makes O(n) average time possible.

Four approaches cover the full range of what a placement or technical interview can ask here. Knowing when to reach for each one, and being able to justify the trade-off, is what separates a correct answer from a strong one.

The Problem Statement

Given an array of n integers (not necessarily sorted, may contain duplicates) and an integer K where 1 <= K <= n, return the value that would appear at index K-1 if the array were sorted in ascending order.

Worked example:

• Input array: {1, 2, 7, 8, 9, 3, 4, 5, 6, 0}, n = 10, K = 5
• Sorted ascending: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
• arr[K-1] = arr[4] = 4
• Output: 4

Two edge cases to note before writing any code. First, K = 1 is always the minimum element. K = n is always the maximum. Second, when the array contains duplicates, the definition still holds: you want the value at index K-1 in the sorted order, counting duplicates as distinct positions.

If you want practice with the simpler special cases K = 1 and K = n, the approach to finding both minimum and maximum in a single pass applies directly.

Approach 1: Sort and Index

Sort the array in ascending order, then return the element at index K-1. Three lines of C++.

Algorithm

• Sort arr ascending.
• Return arr[K - 1].

C++ Code

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int kthSmallestSort(vector<int> arr, int K) {
    sort(arr.begin(), arr.end());
    return arr[K - 1];
}

int main() {
    vector<int> arr = {1, 2, 7, 8, 9, 3, 4, 5, 6, 0};
    int K = 5;
    cout << "5th smallest: " << kthSmallestSort(arr, K) << "\n";
    return 0;
}

Output: 5th smallest: 4

Complexity

• Time: O(n log n), driven by the sort.
• Space: O(1) extra. std::sort is in-place.

The sort-and-index approach modifies the array. Pass a copy if the original order matters. Use this approach when the sorted order is needed for a subsequent step; if only the Kth value is needed, QuickSelect does less work.

Approach 2: QuickSelect

QuickSelect is the partition step of QuickSort, applied selectively. After one partition, the pivot sits at its final sorted position p. If p equals K-1, the pivot is the answer. If p is greater than K-1, recurse on the left subarray. If p is less than K-1, recurse on the right subarray. Only one recursive branch is ever taken, not two.

Algorithm

• Choose a pivot (here: the rightmost element, Lomuto scheme).
• Partition: move elements smaller than or equal to the pivot left, larger elements right.
• Let p be the pivot’s final index.
• If p == K-1, return arr[p].
• If p > K-1, recurse on arr[left..p-1].
• If p < K-1, recurse on arr[p+1..right].

C++ Code

#include <iostream>
#include <vector>
using namespace std;

int partition(vector<int>& arr, int left, int right) {
    int pivot = arr[right];
    int i = left - 1;
    for (int j = left; j < right; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[right]);
    return i + 1;
}

int quickSelect(vector<int>& arr, int left, int right, int k) {
    if (left == right) return arr[left];
    int pivotIdx = partition(arr, left, right);
    if (pivotIdx == k) return arr[pivotIdx];
    if (pivotIdx < k) return quickSelect(arr, pivotIdx + 1, right, k);
    return quickSelect(arr, left, pivotIdx - 1, k);
}

int kthSmallestQS(vector<int>& arr, int K) {
    return quickSelect(arr, 0, (int)arr.size() - 1, K - 1);
}

int main() {
    vector<int> arr = {1, 2, 7, 8, 9, 3, 4, 5, 6, 0};
    int K = 5;
    cout << "5th smallest: " << kthSmallestQS(arr, K) << "\n";
    return 0;
}

Output: 5th smallest: 4

Complexity

• Time: O(n) average, O(n squared) worst case. The worst case occurs when the pivot is always the smallest or largest element (e.g., sorted input with last-element pivot choice).
• Space: O(log n) average call stack depth, O(n) worst case.

The worst-case scenario is avoidable by choosing a random pivot: swap a random element with arr[right] before each partition call. Randomised QuickSelect achieves O(n) expected time with high probability.

Approach 3: Max-Heap of Size K

Build a max-heap of the first K elements. The heap’s root is always the largest value in the heap. For each remaining element in the array, if it is smaller than the root, replace the root with the new element and restore the heap property. After processing all n elements, the root holds the Kth smallest value overall.

The intuition: the heap maintains exactly the K smallest elements seen so far. The root is the largest among them, which by definition is the Kth smallest.

Algorithm

• Build a max-heap from arr[0..K-1].
• For each element arr[i] from index K to n-1:
  • If arr[i] < heap.top(): pop the root, push arr[i].
• Return heap.top().

C++ Code

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int kthSmallestHeap(vector<int>& arr, int K) {
    // Default priority_queue is a max-heap
    priority_queue<int> maxHeap(arr.begin(), arr.begin() + K);
    for (int i = K; i < (int)arr.size(); i++) {
        if (arr[i] < maxHeap.top()) {
            maxHeap.pop();
            maxHeap.push(arr[i]);
        }
    }
    return maxHeap.top();
}

int main() {
    vector<int> arr = {1, 2, 7, 8, 9, 3, 4, 5, 6, 0};
    int K = 5;
    cout << "5th smallest: " << kthSmallestHeap(arr, K) << "\n";
    return 0;
}

Output: 5th smallest: 4

C++ STL’s std::priority_queue is a max-heap by default. The constructor that takes two iterators builds the heap in O(K) time using the heapify algorithm.

Complexity

• Time: O(K) to build the initial heap, then O((n-K) log K) for the remaining elements. Total: O(n log K).
• Space: O(K) for the heap.

This approach does not modify the original array. For K much smaller than n, O(n log K) is close to O(n). For K = 1, it degenerates to a simple minimum scan.

Approach 4: STL nth_element

C++ STL provides std::nth_element, which rearranges the array so that the element at position K-1 is the value that would be there in a sorted array. Elements before position K-1 are all less than or equal to it; elements after are all greater than or equal. Neither subrange is sorted internally.

C++ Code

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int kthSmallestSTL(vector<int> arr, int K) {
    nth_element(arr.begin(), arr.begin() + K - 1, arr.end());
    return arr[K - 1];
}

int main() {
    vector<int> arr = {1, 2, 7, 8, 9, 3, 4, 5, 6, 0};
    int K = 5;
    cout << "5th smallest: " << kthSmallestSTL(arr, K) << "\n";
    return 0;
}

Output: 5th smallest: 4

Complexity

• Time: O(n) average. Introselect in C++11 and later guarantees O(n) worst case, unlike plain QuickSelect.
• Space: O(log n) call stack.

nth_element modifies the array in place. Pass a copy if the original order must be preserved. For production code, nth_element is the preferred single-call solution when the full array is available in memory.

Complexity Comparison

Approach	Time (average)	Time (worst)	Space	Modifies input
Sort and index	O(n log n)	O(n log n)	O(1)	Yes
QuickSelect	O(n)	O(n squared)	O(log n)	Yes
Max-heap of size K	O(n log K)	O(n log K)	O(K)	No
std::nth_element	O(n)	O(n)	O(log n)	Yes

When to use each:

• Sort and index — only when sorted order is needed for a later step, otherwise wasteful.
• QuickSelect — when you want manual control over the algorithm and the worst case is acceptable (randomise the pivot to push it to near-zero probability).
• Max-heap — when K is small relative to n, when input arrives as a stream, or when the original array must stay unmodified.
• std::nth_element — when working with a C++ codebase and want the guaranteed O(n) worst case with a single call.

Placement Interview Patterns

The Kth smallest element problem appears in technical rounds at service-tier and product-tier companies. The question rarely stops at “write a sort-and-return function.” Common follow-up questions:

Can you do better than O(n log n)?

Yes. QuickSelect or nth_element achieve O(n) average. The theoretical lower bound for selection in an unsorted array is O(n). You must inspect every element at least once, and sorting the full array exceeds that bound.

What if the array has duplicates?

All four approaches handle duplicates correctly. The partition step in QuickSelect places elements less than or equal to the pivot on the left, so duplicate values are handled without special-casing. The returned value is always the correct Kth position in sorted order.

What if K equals n/2?

That is the median. The max-heap approach with K = n/2 uses O(n/2) space. nth_element with the midpoint iterator is the most efficient single-call solution.

What if the array does not fit in memory?

The max-heap approach with size K works on streaming input: process elements one at a time, maintain the heap, never hold more than K elements plus the current element in memory. No other approach in this article works on a data stream without materialising the full array first.

For a broader set of array and data-structure problems that appear in Indian IT technical rounds, the 20 most asked data structures interview questions covers the Nth-node-from-end problem, BST search, and hash-table collision strategies alongside the Kth smallest pattern.

The O(n) vs O(n log n) trade-off analysed above is the same type of reasoning that AI engineers apply when choosing between retrieval strategies in large-scale systems. TinkerLLM at ₹299 is a practical starting point if you want to run those experiments yourself rather than only solve them on paper.