279. Kth Smallest Number in Multiplication Table

Build the entire multiplication table as a flat list, sort it, and return the k-th element.

Brute Force

Generate all m * n values by computing i * j for each cell (i from 1 to m, j from 1 to n). Sort the resulting list and return the element at index k - 1.

Sorting m * n values costs O(mn log(mn)) time and O(mn) space.

Why it is slow: For m = n = 30000, the table has 9 * 10^8 entries — far too many to store and sort.

import java.util.ArrayList;
import java.util.Collections;

class Solution {
    public int findKthNumber(int m, int n, int k) {
        ArrayList<Integer> table = new ArrayList<>();
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                table.add(i * j);
            }
        }
        Collections.sort(table);
        return table.get(k - 1);
    }
}

Binary search on the answer value x, counting how many entries in the table are <= x. The count for row i is min(x // i, n), summed over all rows.

Mental Model

Instead of enumerating all entries, ask: for a candidate answer x, how many table entries are at most x? Row i contains i, 2i, 3i, ..., so exactly min(x // i, n) entries are <= x. Summing across all m rows gives the total count in O(m) time. Binary search narrows x until we find the smallest value whose count is >= k.

Algorithm Steps

1. Set lo = 1, hi = m * n.
2. While lo < hi:
   • Compute mid = (lo + hi) // 2.
   • Count entries <= mid: count = sum(min(mid // i, n) for i in 1..m).
   • If count >= k, set hi = mid.
   • Else set lo = mid + 1.
3. Return lo.

Worked Walk-through

m=3, n=3, k=5

Edge Cases

• k = 1: The smallest entry is always 1.
• k = m * n: The largest entry is m * n.
• m = 1 or n = 1: Table is just 1, 2, ..., max(m,n). The k-th value is k.

Complexity

• Time: O(m * log(m * n)) — binary search does O(log(mn)) iterations, each costing O(m) to count.
• Space: O(1) — only a few variables.