Kth Smallest Number in Multiplication Table: Binary Search on Value

May 21, 20265 min read

leetcodeproblemhardbinary-searchmath

Kth Smallest Number in Multiplication Table is LeetCode 668. You are given an m x n multiplication table where the entry in row i, column j is i * j (1-indexed). Your job is to find the kth smallest number in this table.

The naive approach would be to dump every entry into a list, sort it, and return the kth element. That is O(m * n * log(m * n)) time and O(m * n) space. For the constraints in this problem (m and n up to 30,000), that table has up to 900 million entries. You cannot even store it, let alone sort it.

The trick is that you never need to build the table at all. You can binary search on the answer value itself.

Example: m = 3, n = 3, k = 5. The answer is 3.

The 3x3 multiplication table sorted: 1, 2, 2, 3, 3, 4, 6, 6, 9. The 5th smallest is 3. Blue cells have values below 3; green cells equal the answer.

Approach

Here is the key insight. Instead of asking "what is the kth smallest value?", flip the question: "for a candidate value x, how many entries in the table are at most x?"

If you can answer that counting question quickly, you can binary search over the range of possible values [1, m * n] and find the smallest x where the count is at least k. That x is your answer.

The counting step is surprisingly cheap. For row i of the multiplication table, the entries are i, 2i, 3i, ..., ni. The number of entries in row i that are at most x is min(x // i, n). You take the floor division x // i because the entries are multiples of i, and you cap it at n because there are only n columns. Sum that across all m rows, and you have the total count in O(m) time.

The binary search converges in O(log(m * n)) iterations. Each iteration does O(m) work. Total: O(m * log(m * n)). That is fast enough for tables with hundreds of millions of entries.

Binary search on value works here because the multiplication table has a rigid structure. You never need to see or sort the actual entries. For any candidate value, you can count how many entries fall at or below it by scanning one row at a time. That counting function is the key that unlocks the whole problem.

Practice binary search on answer patterns

The Python solution

def findKthNumber(m, n, k):
    lo, hi = 1, m * n
    while lo < hi:
        mid = (lo + hi) // 2
        count = 0
        for i in range(1, m + 1):
            count += min(mid // i, n)
        if count < k:
            lo = mid + 1
        else:
            hi = mid
    return lo

lo = 1, hi = m * n: the smallest possible value in the table is 1 (row 1, column 1), and the largest is m * n (bottom-right corner). The answer must be somewhere in this range.
mid = (lo + hi) // 2: pick the midpoint of the current search range as the candidate value.
Counting loop: for each row i, the number of entries that are at most mid is min(mid // i, n). Sum these across all rows.
if count < k: lo = mid + 1: fewer than k entries are at most mid, so the answer must be strictly larger. Move lo past mid.
else: hi = mid: at least k entries are at most mid, so mid could be the answer (or the answer could be smaller). Keep mid in range.
Return lo: when lo == hi, the search has converged to a single value. That is the kth smallest.

Be careful with the condition. When count is at least k, you set hi = mid (not hi = mid - 1). The current mid might actually be the answer, so you cannot exclude it. This is the same boundary logic as in Koko Eating Bananas and other binary-search-on-answer problems.

Drill binary search on answer patterns with spaced repetition

Visual walkthrough

Let's trace the binary search for m = 3, n = 3, k = 5. The search range starts at [1, 9].

Step 1: lo=1, hi=9, mid=5

Row 1: min(5, 3) = 3 | Row 2: min(2, 3) = 2 | Row 3: min(1, 3) = 1

count = 3 + 2 + 1 = 6

count = 6, which is at least k=5. The answer could be 5 or smaller. Set hi = 5.

Step 2: lo=1, hi=5, mid=3

Row 1: min(3, 3) = 3 | Row 2: min(1, 3) = 1 | Row 3: min(1, 3) = 1

count = 3 + 1 + 1 = 5

count = 5, which is at least k=5. The answer could be 3 or smaller. Set hi = 3.

Step 3: lo=1, hi=3, mid=2

Row 1: min(2, 3) = 2 | Row 2: min(1, 3) = 1 | Row 3: min(0, 3) = 0

count = 2 + 1 + 0 = 3

count = 3, which is less than k=5. We need a larger value. Set lo = mid + 1 = 3.

Step 4: lo=3, hi=3. Done!

Answer: 3

lo equals hi. The 5th smallest number in the 3x3 multiplication table is 3.

Four steps and we have the answer. Even if m and n were 30,000, giving a search range up to 900,000,000, binary search would still converge in about 30 iterations. Each iteration scans m rows, so the total work is modest.

Complexity analysis

Metric	Value	Why
Time	`O(m * log(m * n))`	Binary search over `m * n` values; each iteration counts in O(m)
Space	`O(1)`	Only a few integer variables

Building blocks

This problem combines two ideas:

Binary search on the answer: instead of searching a sorted array, you search a range of candidate values and use a predicate to decide which half to keep. You have seen this in Koko Eating Bananas (search on speed) and Kth Smallest Element in a Sorted Matrix (search on value with counting).
Counting in structured data: the multiplication table has enough structure that you can count how many entries are at most some value x in O(m) time, without ever building the table. This is the feasibility check that powers the binary search.

Edge cases

k = 1: the smallest entry is always 1 (row 1, column 1). The binary search returns 1 naturally.
k = m * n: the largest entry is m * n (bottom-right corner). The count for x = m * n is m * n, which is at least k.
m = 1 or n = 1: the table is a single row or column. The entries are 1, 2, ..., n (or 1, 2, ..., m), already sorted. The binary search still works, though a direct index would also do.
Duplicate values: the multiplication table contains many duplicates (for example, 6 appears twice in a 3x3 table). The binary search handles duplicates correctly because it finds the smallest x where the count reaches k, not a specific position.

From understanding to recall

The logic is clean: binary search on the candidate value, count how many table entries are at most that value, narrow the range. You probably follow it right now.

But imagine writing this cold in an interview. Do you remember that the count for row i is min(mid // i, n)? Do you recall whether the condition is count < k (move lo up) or count > k (move hi down)? These details blur together after a week.

Spaced repetition fixes this. You write the solution from scratch today, again tomorrow, then in three days. After a few rounds, the counting formula and the binary search boundary logic become second nature. You do not rederive them under pressure. You just write them.

Try CodeBricks free

Koko Eating Bananas - Another binary search on the answer
Find the Duplicate Number - Binary search on value range
Kth Smallest Element in a Sorted Matrix - Similar count-based binary search