Start learning free

LESSON 254 OF 347 · BINARY SEARCH

Smallest K in C#: Binary Search on the Value of the K-th Number

Practice O(n log n) Read the full explanation

Given an array of positive integers nums, return the smallest k values, in any order you want.

Example:

Input: nums = [5, 9, 3, 6, 2, 1, 3, 2, 7, 5], k = 4
Output: [1, 2, 2, 3]
Explanation: Smallest number is 1, 2nd smallest is 2, 
            3rd smallest is 2, 4th smallest is 3

The result can be in any order, [2, 1, 3, 2] is also a correct answer.

Note:

For this lesson, your algorithm should run in O(n log n) time.


STEP 1 OF 3
    Ctrl + Enter to check

    C# · BINARY SEARCH

    Smallest K in C#, explained

    Problem overview

    KSmallest receives an int[] nums of positive integers and an int k. It returns an array of the k smallest values, in any order. Duplicates count separately: for nums = {5, 9, 3, 6, 2, 1, 3, 2, 7, 5} and k = 4, the four smallest are 1, 2, 2 and 3, so {1, 2, 2, 3} and {2, 1, 3, 2} are both correct.

    The lesson wants a solution that runs in O(n log n) time. Sorting the whole array and taking the first k values would meet that, and this lesson reaches a similar cost by a different route.

    Approach: find the k-th smallest value, then collect

    Once you know the value of the k-th smallest number, call it kthNum, the answer is easy to assemble:

    • every number strictly below kthNum is in the answer;
    • the answer is then topped up with copies of kthNum until it has k values.

    The top-up is needed because kthNum can appear several times in nums. In the example, kthNum is 3. Only the values 1, 2 and 2 are strictly smaller, so the answer gets one copy of 3 to reach four values.

    How do we find kthNum without sorting? By binary searching on the value instead of on an index. For a candidate value val, count how many numbers in nums are less than val. If that count is less than k, then val could be the k-th smallest or lie below it, so remember it and try larger values. If the count is at least k, val is too large, so try smaller ones. The largest value that passes the test is the k-th smallest number.

    Here is the search on the example, where the values range from 1 to 9. The candidates tried are 5 (5 numbers are smaller, too many), 2 (1 smaller, remember 2), 3 (3 smaller, remember 3) and 4 (5 smaller, too many). The last remembered value is 3, which is the 4th smallest.

    Step by step

    1. Write HowManyLess(nums, val). Keep a counter at 0, loop over nums with foreach (int num in nums), add one when val > num, and return the counter. A single LINQ expression could count too, but the loop makes the logic plain.
    2. Write KSmallestNum(nums, k) above it. Start left and right at the minimum and maximum of nums, obtained with Min() and Max(), and start result at left.
    3. Loop while left <= right. Take val = left + (right - left) / 2, and store HowManyLess(nums, val) in smaller.
    4. If smaller < k, save val in result and set left = val + 1 to look for a larger value that still passes. Otherwise set right = val - 1.
    5. Return result at the end.
    6. In KSmallest, store KSmallestNum(nums, k) in kthNum and create result as an int[] of length k. A variable i starts at 0 as the next free position.
    7. Copy the strictly smaller values. Loop over nums and write every value below kthNum to result[i++]. At most k - 1 values are strictly smaller than the k-th smallest, so this never writes past the end.
    8. Pad with kthNum. While i < k, fill the rest of the array with kthNum, then return result.

    The solution in C#

    class Solution {

    public int KSmallestNum(int[] nums, int k) {
        int left = nums.Min();
        int right = nums.Max();
        int result = left;
        while (left <= right) {
            int val = left + (right - left) / 2;
            int smaller = HowManyLess(nums, val);
            if (smaller < k) {
                result = val;
                left = val + 1;
            } else {
                right = val - 1;
            }
        }
        return result;
    }

    public int HowManyLess(int[] nums, int val) {
        int counter = 0;
        foreach (int num in nums) {
            if (val > num) {
                counter++;
            }
        }
        return counter;
    }

    public int[] KSmallest(int[] nums, int k) {
        int kthNum = KSmallestNum(nums, k);
        int[] result = new int[k];
        int i = 0;
        foreach (int val in nums) {
            if (val < kthNum) {
                result[i++] = val;
            }
        }
        while (i < k) {
            result[i++] = kthNum;
        }
        return result;
    }
}

    C# details worth knowing

    • Min() and Max(). They are LINQ extension methods from System.Linq and work on any array of numbers. Both throw an InvalidOperationException on an empty array, so the solution assumes nums is not empty.
    • result[i++]. Post-increment uses the current value of i as the index, then moves i forward. It writes and advances in one expression.
    • Two variables named result. KSmallestNum and KSmallest each have their own local result, one an int and the other an int[]. They don't interfere because each lives in its own method.
    • Arrays have a fixed length. new int[k] allocates exactly k slots, filled with zeros. That is why the code tracks i by hand instead of appending, as a List<int> would allow.
    • The midpoint form. left + (right - left) / 2 never adds the two bounds, so it can't overflow for large values the way (left + right) / 2 could.

    Complexity

    Each call to HowManyLess is a pass over the array, O(n). The binary search halves the range of values, so it needs about log₂(max - min) rounds, at most 31 for int values. The search therefore costs O(n log V), where V is the spread between the smallest and largest value. Finding Min() and Max() and building the answer are each one more O(n) pass.

    The result array holds k numbers, so the extra space is O(k). The search itself uses O(1).

    Edge cases and common mistakes

    • Forgetting the padding. With duplicates of the k-th value, fewer than k numbers are strictly smaller. Without the final while loop, the unfilled slots stay 0. For the example, the result would be {2, 1, 2, 0}.
    • Counting with <= instead of <. The test "fewer than k numbers are below val" is what makes the largest passing value the k-th smallest. A different comparison shifts the answer.
    • Copying values equal to kthNum in the first loop. That could write more than k values, and the extra writes run off the end of the array and throw an IndexOutOfRangeException.
    • k equal to the array length. Then the k-th smallest is the maximum, and the result contains every number.
    • Missing using System.Linq;. In a plain C# file, nums.Min() only compiles with that directive.

    Testing

    numskresult, in any order
    {5, 9, 3, 6, 2, 1, 3, 2, 7, 5}4{2, 1, 2, 3}
    {4, 4, 4}2{4, 4}
    {3, 1, 2}3{1, 2, 3}
    Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free