Skip to content
Work Practice Products Coding interviews Machine learning coding Quant developer HFT course Blog Method Why me About Enquire Book a call

Coding · Binary search

The pattern: the k-th smallest by counting

Lesson · 12 min read · Binary search · Pattern: the k-th smallest by counting

When the values cannot all be listed, search over the value itself: the k-th smallest is the first v with at least k values at or below it.

Search the value, count the rest

Some k-th smallest questions come with far too many values to sort: a multiplication table with 9 × 10⁸ cells, every pairwise distance in an array of 10⁴ numbers. But counting how many values are at most v is often cheap, and that count only grows as v grows. So the k-th smallest is a first-true search:

k-th smallest by counting

kth(k)

  1. count(v) = how many values are ≤ v. It never decreases as v increases.
  2. lo = the smallest value, hi = the largest.
  3. First-true search for the first v with count(v) ≥ k.
  4. Return lo.
112answer 4
The test count(v) ≥ k along the values. Below the answer too few values are small enough; from the answer on, at least k are.

Why the answer is a real value

The search runs over every integer in the range, most of which may not appear among the values at all. The answer still does. At the returned v, count(v) ≥ k but count(v − 1) < k, so some value equals v exactly: the count went up between v − 1 and v. No separate check is needed.

Worked example: a multiplication table

In the m × n table the row i holds i, 2i, …, n × i. The values at most v in row i number min(⌊v / i⌋, n), so count(v) is a sum over the m rows: O(m) per test, and no table is built.

The 7th smallest value of the 3 × 4 multiplication table.

  1. Step 1 / 6
    lo 1hi 1212341123422468336912
    k7

    The 3 × 4 table, drawn only to show the counts. Values run from 1 to 12.

  2. Step 2 / 6
    lo 1hi 12mid 6 ✓12341123422468336912
    lo1mid6hi12count9

    count(6) = min(6/1, 4) + min(6/2, 4) + min(6/3, 4) = 4 + 3 + 2 = 9. At least 7: hi = 6.

  3. Step 3 / 6
    lo 1hi 612mid 3 ✗12341123422468336912
    lo1mid3hi6count5

    count(3) = min(3/1, 4) + min(3/2, 4) + min(3/3, 4) = 3 + 1 + 1 = 5. Fewer than 7: lo = 4.

  4. Step 4 / 6
    1lo 4hi 612mid 5 ✓12341123422468336912
    lo4mid5hi6count7

    count(5) = min(5/1, 4) + min(5/2, 4) + min(5/3, 4) = 4 + 2 + 1 = 7. At least 7: hi = 5.

  5. Step 5 / 6
    1lo 4hi 512mid 4 ✓12341123422468336912
    lo4mid4hi5count7

    count(4) = min(4/1, 4) + min(4/2, 4) + min(4/3, 4) = 4 + 2 + 1 = 7. At least 7: hi = 4.

  6. Step 6 / 6
    112answer 412341123422468336912
    answer4

    lo = hi = 4: count(4) = 7 ≥ 7 and count(3) = 5 < 7. The answer is 4.

TimeO(m log(m × n))
SpaceO(1)

Against O(m × n log(m × n)) to build and sort the table.

Three counting functions

The search is identical in every problem of this module. The work is in counting fast.

Problemcount(v): values ≤ vCost per count
k-th smallest in a multiplication tableΣ over rows i of min(⌊v / i⌋, n)O(m)
k-th smallest in a row-and-column-sorted matrixstaircase walk from the bottom-left corner, adding the cells above each stepO(n)
k-th smallest pair distancesort once; for each right end, two pointers find how many earlier values are within vO(n)

A heap also finds the k-th smallest by popping k times, at O(k log n). It wins when k is small; counting wins when k can be as large as the number of values, which is how these problems are usually set.

Problems in this module