Kth Smallest Number in Multiplication Table

Hard Binary Search Binary Search on Answer Space Original on LeetCode

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^4
  • 1 <= 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.

00:00
Testcase

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.

ApproachTimeSpace
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)

TimeO(mn log(mn))Sorting all m × n products.
SpaceO(mn)Every product is stored.

Write out all m × n products, sort them, and return the one at index k - 1.

  1. For i in 1 … m, j in 1 … n: add i × j.
  2. 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];
    }
}

2Better (min-heap merge of the rows)

TimeO(m log m + k log m)Building the heap, then k pops and pushes on a heap of size m.
SpaceO(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.

  1. Push (i, i, 1) for every row i (value, row, column).
  2. Pop k - 1 times; after popping (v, i, j), push (v + i, i, j + 1) if j < n.
  3. 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];
    }
}

3Optimal (binary search on the value)

TimeO(m log(mn))About log(m × n) ≈ 30 rounds, each counting over m rows.
SpaceO(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.

  1. lo = 1, hi = m × n.
  2. While lo < hi: mid = lo + (hi - lo) / 2; if count(mid) >= k, hi = mid, else lo = mid + 1.
  3. count(x) = sum over i = 1 … m of min(x / i, n) (stop early once x / i is 0).
  4. 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;
    }
}

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.