Kth Smallest Number in Multiplication Table
Hard · Binary Search · Math · Binary Search
Problem
An m × n multiplication table holds i · j in row i, column j (both counted from 1), so it contains m · n values, many of them repeated.
Given m, n and k, return the k-th smallest value in the table, counting repeats.
The table can hold close to a billion values, so it cannot be built.
Examples
Input: m = 3, n = 4, k = 7 Output: 4
Sorted, the table is 1, 2, 2, 3, 3, 4, 4, 6, 6, 8, 9, 12, and the 7th value is 4.
Input: m = 2, n = 2, k = 4 Output: 4
The table is [[1, 2], [2, 4]], and its 4th smallest value is the largest, 4.
Input: m = 1, n = 5, k = 2 Output: 2
A single row is just 1, 2, 3, 4, 5.
Constraints
- 1 <= m, n <= 3 · 10^4
- 1 <= k <= m · n
Approaches
- Baseline: build the table and sort it — time O(m · n · log(m · n)), space O(m · n)
Follow-up
The same search finds the k-th smallest of any table whose rows are sorted and can be counted quickly, such as the products of two sorted lists (the second use case), or the pair distances of an array. Can you count each row in O(1) and the whole table in O(m), as here, or does the count need two pointers?
Related problems
Start free on Cariara · Coding problems · System design studio
