Given an unsorted integer array arr and a positive integer k, return the value occupying position k in ascending sorted order. Repeated values occupy separate positions, and k uses 1-based ranking.
Example 1
Input: arr = [10, 5, 4, 3, 48, 6, 2, 33, 53, 10], k = 4
Output: 5
Explanation: Ascending order becomes [2, 3, 4, 5, 6, 10, 10, 33, 48, 53]. Position 4 contains 5.
Example 2
Input: arr = [-5], k = 1
Output: -5
Explanation: A single value occupies the first sorted position.
Brute Force Approach
Sorting the array in ascending order places every element at its correct rank. Since array indexing starts from 0, the k-th smallest element appears at index k - 1.
This approach is simple and easy to verify, but it sorts the entire array even though only one ranked value is required.
Algorithm
Sort
arrin ascending order so every element reaches its correct sorted position.Keep duplicate values as separate elements because each occurrence has its own rank.
Calculate
targetIndex = k - 1because the given rank is 1-based while array indexing is 0-based.Return
arr[targetIndex]because this position contains the k-th smallest element.
Dry Run
kth-smallest Element in array Brute Force
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Finds the value at sorted rank k. int kthSmallest(vector<int>& arr, int k) { // Arrange every value in ascending order. sort(arr.begin(), arr.end()); // Convert the 1-based rank to an array index. int targetIndex = k - 1; // Return the value occupying the required rank. return arr[targetIndex]; }};// Driver codeint main() { vector<int> arr = {7, 10, 4, 3, 20, 15}; int k = 3; Solution obj; cout << obj.kthSmallest(arr, k) << endl; return 0;}Complexity Analysis
Time Complexity: O(N log N), where N is the number of elements in the array, because sorting arranges all N values before one constant-time index lookup.
Space Complexity: O(N), because sorting may require auxiliary storage depending on the language and sorting implementation.
Better Approach
Sorting the entire array does unnecessary work because only the k smallest values matter. A max-heap of size k keeps just these useful candidates, with the largest among them always available at the root.
Whenever the heap grows beyond k, remove its largest value because it cannot remain among the current k smallest elements. After processing the whole array, the heap contains the k smallest occurrences, so its root is the k-th smallest element.
Algorithm
Create an empty max-heap so the largest retained candidate always stays at the root.
Traverse every value in
arrso each element gets a chance to enter the smallestkcandidates.Push the current value into the heap because it may belong among the
ksmallest elements.If the heap size becomes greater than
k, remove the root because the largest candidate is no longer needed.Keep duplicate values as separate heap entries because each occurrence has its own sorted rank.
After processing all elements, return the heap root because it is the largest value among the final
ksmallest elements, making it the k-th smallest.
Dry Run
kth-smallest better
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Finds sorted rank k with a bounded max-heap. int kthSmallest(vector<int>& arr, int k) { // Store only the smallest useful candidates. priority_queue<int> maxHeap; // Process every array value once. for (int value : arr) { // Add the current value to the candidate set. maxHeap.push(value); // Excess size means the largest value is useless. if ((int)maxHeap.size() > k) { // Discard the largest current candidate. maxHeap.pop(); } } // The largest retained candidate has rank k. return maxHeap.top(); }};// Driver codeint main() { vector<int> arr = {7, 10, 4, 3, 20, 15}; int k = 3; Solution obj; cout << obj.kthSmallest(arr, k) << endl; return 0;}Complexity Analysis
Time Complexity: O(N log k), where N is the number of elements in the array, because each element is inserted into the heap and may cause one removal from a heap of size at most k.
Space Complexity: O(k), because the max-heap stores at most k candidate elements.
Optimal Approach
The k-th smallest element only needs to reach its correct sorted position, so sorting the complete array is unnecessary. Quickselect uses partitioning to keep only the part of the array that can still contain the target index k - 1.
A three-way partition separates values into smaller, equal, and greater groups around a pivot. If the target lies inside the equal group, the answer is found. Otherwise, only the left or right side is kept. Random pivot selection helps avoid repeatedly poor partitions and gives expected linear time.
Algorithm
Convert the given rank into
targetIndex = k - 1because array indexing starts from0.Set
left = 0andright = n - 1so the complete array is initially considered.If
left == right, returnarr[left]because only one possible candidate remains.Choose a random pivot from the active range to reduce the chance of consistently unbalanced partitions.
Partition the active range into:
Values smaller than the pivot.
Values equal to the pivot.
Values greater than the pivot.
Compare
targetIndexwith the equal-value range:If it lies inside the range, return the pivot because the required rank has been found.
If it lies before the range, continue only with the left part.
Otherwise, continue only with the right part.
Repeat until the k-th smallest element is found.
Dry Run
k-th-smallest-element-in-an-array-optimal-heading-preserved-color-fixed-final.png
Solution
#include <bits/stdc++.h>using namespace std;class Solution {private: // Groups values around a random pivot value. pair<int, int> threeWayPartition( vector<int>& arr, int left, int right ) { // Choose a random pivot value from the active range. int span = right - left + 1; int pivotIndex = left + rand() % span; int pivotValue = arr[pivotIndex]; int smaller = left; int current = left; int greater = right; // Build smaller, equal, and greater regions. while (current <= greater) { // A smaller value belongs at the range front. if (arr[current] < pivotValue) { swap(arr[smaller], arr[current]); smaller++; current++; continue; } // A greater value belongs at the range back. if (arr[current] > pivotValue) { swap(arr[current], arr[greater]); greater--; continue; } // An equal value already occupies the middle. current++; } // Return the inclusive equal-value interval. return {smaller, greater}; }public: // Finds sorted rank k with iterative Quickselect. int kthSmallest(vector<int>& arr, int k) { int left = 0; int right = arr.size() - 1; // Convert the required rank to a zero-based index. int targetIndex = k - 1; // Shrink the active range until the rank is found. while (left <= right) { // A single active value must be the answer. if (left == right) { return arr[left]; } // Group the active range around one pivot value. pair<int, int> equalRange = threeWayPartition(arr, left, right); // A lower target requires the left partition. if (targetIndex < equalRange.first) { right = equalRange.first - 1; continue; } // A higher target requires the right partition. if (targetIndex > equalRange.second) { left = equalRange.second + 1; continue; } // The target lies inside the equal-value interval. return arr[targetIndex]; } return -1; }};// Driver codeint main() { vector<int> arr = {7, 10, 4, 3, 20, 15}; int k = 3; Solution obj; cout << obj.kthSmallest(arr, k) << endl; return 0;}Complexity Analysis
Time Complexity: O(N) on average, where N is the number of elements in the array, because randomized partitioning discards one side after each scan. In the worst case, repeatedly unbalanced partitions lead to O(N2) time.
Space Complexity: O(1), because iterative Quickselect partitions the array in place using only a fixed number of variables.
Interview follow-up Questions
Yes. Every occurrence occupies its own position in sorted order. Therefore, equal values can occupy multiple consecutive ranks unless the problem specifically asks for the kth distinct smallest element.
Be the first to add a comment.