Problem overview
The method kSmallest receives an array of positive integers, nums, and a number k. It returns the k smallest values, in any order. Duplicates count separately.
In the example, nums = [5, 9, 3, 6, 2, 1, 3, 2, 7, 5] and k = 4. Sorted, the array begins 1, 2, 2, 3, so the answer is [1, 2, 2, 3], and [2, 1, 3, 2] is accepted too. The lesson's target is O(n log n) time.
Approach: find the k-th smallest value, then collect
Sorting the array and taking the first k elements is the obvious solution. This lesson takes another route that never sorts: first find the value of the k-th smallest element, then pick the elements that fall below it.
To find that value, binary search over the range of values, not the indices. For a candidate value val, count how many elements are strictly less than it. If that count is smaller than k, the k-th smallest element is val or something larger, so val is a possible answer and the search continues above it. Otherwise at least k elements are below val, so the k-th smallest is smaller than val, and the search continues below it. The last possible answer saved is the k-th smallest value.
On the example, the values range from 1 to 9. The candidate 5 has five smaller elements, which is at least 4, so the search goes lower. The candidate 2 has one smaller element, so 2 is saved and the search goes higher. The candidate 3 has three smaller elements (2, 2 and 1), so 3 is saved. The candidate 4 has five smaller elements, so the search goes lower and ends. The k-th smallest value is 3.
Collecting is not quite finished by taking everything smaller than 3, which gives only 1, 2 and 2: three elements. The fourth is a copy of 3 itself. A value that occurs several times may need to be added a few times, so the code pads the result with the k-th value until it holds k numbers.
Step by step
- Write
howManyLess(nums, val). Startcounterat 0, loop over the indices, add one whenval > nums[i], and returncounter. - Write
kSmallestNum(nums, k). Startleftandrightatnums[0]. Afor...ofloop overnumsappliesMath.mintoleftandMath.maxtoright, so they end as the smallest and largest values. - Start
resultatleft. It is the smallest value, a safe answer if nothing better is found. - Loop while
left <= right. Takeval = left + Math.floor((right - left) / 2)and count the smaller elements withthis.howManyLess(nums, val). Both areconstbecause each pass makes new ones. - If
smaller < k, savevalinresultand setleft = val + 1. - Otherwise set
right = val - 1. Returnresultafter the loop. - Finish
kSmallest. Storethis.kSmallestNum(nums, k)inconst kthNum, and create an emptyconst result: number[]. - Push everything smaller than
kthNumin a loop over the indices. - Pad with
kthNum. A second loop startsiatresult.lengthand stops beforek, pushingkthNumeach time. Returnresult.
The solution in TypeScript
class Solution {
kSmallestNum(nums: number[], k: number): number {
let left = nums[0];
let right = nums[0];
for (const num of nums) {
left = Math.min(left, num);
right = Math.max(right, num);
}
let result = left;
while (left <= right) {
const val = left + Math.floor((right - left) / 2);
const smaller = this.howManyLess(nums, val);
if (smaller < k) {
result = val;
left = val + 1;
} else {
right = val - 1;
}
}
return result;
}
howManyLess(nums: number[], val: number): number {
let counter = 0;
for (let i = 0; i < nums.length; i++) {
if (val > nums[i]) {
counter++;
}
}
return counter;
}
kSmallest(nums: number[], k: number): number[] {
const kthNum = this.kSmallestNum(nums, k);
const result: number[] = [];
for (let i = 0; i < nums.length; ++i) {
if (nums[i] < kthNum) {
result.push(nums[i]);
}
}
for (let i = result.length; i < k; ++i) {
result.push(kthNum);
}
return result;
}
}
Some TypeScript details:
- The annotation on the empty array.
const result: number[] = [];tells the compiler what the array will hold. Without it, the type of an empty array literal can't be inferred. constarrays can still change.constonly stops the variable from being assigned again.pushchanges the array's contents, which is allowed.- Whole-number midpoints.
numberis a double, so/ 2can give2.5.Math.floorfixes that. The search steps by exactly 1, so it only makes sense for integers, as the lesson promises. - Methods through
this. The helpers are called asthis.howManyLessandthis.kSmallestNum. - Passing the array. Arrays are passed by reference, so the helpers read the caller's array without copying it. None of them changes it.
Complexity
Time. Each pass of the search calls howManyLess, which costs O(n). The number of passes is the logarithm of the value range, log(max - min). Collecting is O(n + k). The total is O(n log(max - min)), which is within the lesson's O(n log n) whenever the range of values is no more than polynomial in n. Note that it does not depend on the order of the input.
Space: O(k). The result holds k numbers, and the search itself uses a few variables.
Edge cases and common mistakes
- Duplicates of the k-th value. This is why the padding loop exists. With
[4, 4, 4]andk = 2nothing is smaller than 4, and the padding supplies two 4s. - Counting
<=instead of<. The testsmaller < krelies on a strict count. Changing one without the other shifts the answer by a value. kequal to the length. The result is the whole array, though not necessarily in its original order. For the example array andk = 10, the code returns the elements smaller than 9 and then one 9 at the end.- One element.
[7]withk = 1gives[7]. k = 0. The result is empty.- Non-integer values. Moving
leftbyval + 1can skip values between two integers, so this search is meant for integers only. - Binary search on indices. The array is not sorted, so searching its indices would be wrong. The search here runs over values, which are ordered.
Testing
nums = [5, 9, 3, 6, 2, 1, 3, 2, 7, 5],k = 4gives[2, 1, 2, 3], which has the same values as[1, 2, 2, 3].- The same array with
k = 1gives[1]. nums = [4, 4, 4],k = 2gives[4, 4].nums = [7],k = 1gives[7].