Kth Smallest Number in Multiplication Table
Kth Smallest Number in Multiplication Table is a hard binary search problem solved with the binary search on answer space pattern.
The best approach, optimal (binary search on the value), runs in O(m log(mn)) time and O(1) space.
Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (build and sort) up.
Problem
An m x n multiplication table has the value i * j in row i, column j (both 1-indexed).
Given m, n and k, return the k-th smallest value in the table, counting duplicates (so the answer is the value at position k if all m * n entries were sorted in ascending order).
Examples
Example 1
- Input
m = 3, n = 4, k = 7- Output
4- Why
- The table holds 1, 2, 3, 4 / 2, 4, 6, 8 / 3, 6, 9, 12. Sorted: 1, 2, 2, 3, 3, 4, 4, 6, 6, 8, 9, 12, and the 7th value is 4.
Example 2
- Input
m = 2, n = 5, k = 10- Output
10- Why
- k = m × n asks for the largest entry, which is 2 × 5.
Example 3
- Input
m = 1, n = 6, k = 2- Output
2- Why
- A single row is just 1 … 6.
Constraints
1 <= m, n <= 3 * 10^41 <= k <= m * n
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (build and sort) | O(mn log(mn)) | O(mn) |
| Better (min-heap merge of the rows) | O(m log m + k log m) | O(m) |
| Optimal (binary search on the value) | O(m log(mn)) | O(1) |
1Brute force (build and sort)
O(mn log(mn))Sorting all m × n products.O(mn)Every product is stored.Write out all m × n products, sort them, and return the one at index k - 1.
- For i in 1 … m, j in 1 … n: add i × j.
- Sort; return element k - 1.
class Solution {
public int findKthNumber(int m, int n, int k) {
int[] all = new int[m * n];
int idx = 0;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
all[idx++] = i * j;
Arrays.sort(all);
return all[k - 1];
}
}class Solution:
def findKthNumber(self, m: int, n: int, k: int) -> int:
values = [i * j for i in range(1, m + 1) for j in range(1, n + 1)]
values.sort()
return values[k - 1]class Solution {
public:
int findKthNumber(int m, int n, int k) {
vector<int> all;
all.reserve((size_t)m * n);
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
all.push_back(i * j);
sort(all.begin(), all.end());
return all[k - 1];
}
};function findKthNumber(m, n, k) {
const all = [];
for (let i = 1; i <= m; i++)
for (let j = 1; j <= n; j++)
all.push(i * j);
all.sort((a, b) => a - b);
return all[k - 1];
}2Better (min-heap merge of the rows)
O(m log m + k log m)Building the heap, then k pops and pushes on a heap of size m.O(m)One entry per row.Every row is already sorted (i, 2i, 3i, …). Merge the m rows with a min-heap holding the next value of each row, and pop k times; the k-th pop is the answer.
- Push (i, i, 1) for every row i (value, row, column).
- Pop k - 1 times; after popping (v, i, j), push (v + i, i, j + 1) if j < n.
- The top of the heap is the answer.
class Solution {
public int findKthNumber(int m, int n, int k) {
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
for (int i = 1; i <= m; i++) heap.offer(new int[] { i, i, 1 });
for (int t = 1; t < k; t++) {
int[] cur = heap.poll();
if (cur[2] < n) heap.offer(new int[] { cur[0] + cur[1], cur[1], cur[2] + 1 });
}
return heap.peek()[0];
}
}class Solution:
def findKthNumber(self, m: int, n: int, k: int) -> int:
heap = [(i, i, 1) for i in range(1, m + 1)]
heapq.heapify(heap)
for _ in range(k - 1):
v, i, j = heapq.heappop(heap)
if j < n:
heapq.heappush(heap, (v + i, i, j + 1))
return heap[0][0]class Solution {
public:
int findKthNumber(int m, int n, int k) {
priority_queue<array<int, 3>, vector<array<int, 3>>, greater<array<int, 3>>> heap;
for (int i = 1; i <= m; i++) heap.push({i, i, 1});
for (int t = 1; t < k; t++) {
auto cur = heap.top();
heap.pop();
if (cur[2] < n) heap.push({cur[0] + cur[1], cur[1], cur[2] + 1});
}
return heap.top()[0];
}
};class MinHeap {
constructor(cmp = (a, b) => a - b) { this.a = []; this.cmp = cmp; }
size() { return this.a.length; }
isEmpty() { return this.a.length === 0; }
peek() { return this.a[0]; }
push(x) {
const a = this.a;
a.push(x);
let i = a.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (this.cmp(a[i], a[p]) >= 0) break;
[a[i], a[p]] = [a[p], a[i]];
i = p;
}
}
pop() {
const a = this.a, top = a[0], last = a.pop();
if (a.length > 0) {
a[0] = last;
let i = 0;
while (true) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < a.length && this.cmp(a[l], a[m]) < 0) m = l;
if (r < a.length && this.cmp(a[r], a[m]) < 0) m = r;
if (m === i) break;
[a[i], a[m]] = [a[m], a[i]];
i = m;
}
}
return top;
}
}
function findKthNumber(m, n, k) {
const heap = new MinHeap((a, b) => a[0] - b[0]);
for (let i = 1; i <= m; i++) heap.push([i, i, 1]);
for (let t = 1; t < k; t++) {
const [v, i, j] = heap.pop();
if (j < n) heap.push([v + i, i, j + 1]);
}
return heap.peek()[0];
}3Optimal (binary search on the value)
O(m log(mn))About log(m × n) ≈ 30 rounds, each counting over m rows.O(1)A few integers.Let count(x) be the number of table entries <= x; row i contributes min(x / i, n). count is non-decreasing in x, so binary search over [1, m × n] for the smallest x with count(x) >= k. That x is guaranteed to be a value in the table, because count only jumps at table values.
- lo = 1, hi = m × n.
- While lo < hi: mid = lo + (hi - lo) / 2; if count(mid) >= k, hi = mid, else lo = mid + 1.
- count(x) = sum over i = 1 … m of min(x / i, n) (stop early once x / i is 0).
- Return lo.
class Solution {
public int findKthNumber(int m, int n, int k) {
int lo = 1, hi = m * n;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (count(mid, m, n) >= k) hi = mid;
else lo = mid + 1;
}
return lo;
}
private long count(int x, int m, int n) {
long total = 0;
for (int i = 1; i <= m; i++) {
int inRow = Math.min(x / i, n);
if (inRow == 0) break;
total += inRow;
}
return total;
}
}class Solution:
def findKthNumber(self, m: int, n: int, k: int) -> int:
lo, hi = 1, m * n
while lo < hi:
mid = (lo + hi) // 2
if self.count(mid, m, n) >= k:
hi = mid
else:
lo = mid + 1
return lo
def count(self, x: int, m: int, n: int) -> int:
total = 0
for i in range(1, m + 1):
in_row = min(x // i, n)
if in_row == 0:
break
total += in_row
return totalclass Solution {
public:
int findKthNumber(int m, int n, int k) {
int lo = 1, hi = m * n;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (count(mid, m, n) >= k) hi = mid;
else lo = mid + 1;
}
return lo;
}
private:
long long count(int x, int m, int n) {
long long total = 0;
for (int i = 1; i <= m; i++) {
int inRow = min(x / i, n);
if (inRow == 0) break;
total += inRow;
}
return total;
}
};function findKthNumber(m, n, k) {
let lo = 1, hi = m * n;
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (count(mid, m, n) >= k) hi = mid;
else lo = mid + 1;
}
return lo;
}
function count(x, m, n) {
let total = 0;
for (let i = 1; i <= m; i++) {
const inRow = Math.min(Math.floor(x / i), n);
if (inRow === 0) break;
total += inRow;
}
return total;
}Edge cases to test
- k = 1 (always 1) and k = m × n (always m × n)
- A single row or a single column
- Values repeated many times in the table (k falls inside a block of equal values)
- m × n is up to 9 × 10^8: the table cannot be built
Hints
Hint 1
Building and sorting the table works for small sizes. What is the largest table you could ever afford?
Hint 2
Instead of finding the k-th value directly, ask: for a candidate x, how many entries are <= x? Row i contributes min(x / i, n).
Hint 3
That count only grows as x grows, so binary search for the smallest x whose count reaches k.
FAQ
What is the best time complexity for Kth Smallest Number in Multiplication Table?
Optimal (binary search on the value) runs in O(m log(mn)) time and O(1) extra space. About log(m × n) ≈ 30 rounds, each counting over m rows.
Which pattern does Kth Smallest Number in Multiplication Table use?
It is a binary search problem that uses the binary search on answer space pattern. Other problems with the same pattern: Koko Eating Bananas, Minimum Number of Days to Make m Bouquets, Separate Squares I.
Is there a brute force solution for Kth Smallest Number in Multiplication Table?
Yes. Brute force (build and sort) takes O(mn log(mn)) time and O(mn) space. Write out all m × n products, sort them, and return the one at index k - 1.
Which edge cases should I test for Kth Smallest Number in Multiplication Table?
k = 1 (always 1) and k = m × n (always m × n); A single row or a single column; Values repeated many times in the table (k falls inside a block of equal values); m × n is up to 9 × 10^8: the table cannot be built.