Kth Smallest Number in Multiplication Table - Video Solutions

Problem Overview: You are given an m x n multiplication table where the value at (i, j) is i * j. The task is to return the k-th smallest number among all values in the table without explicitly building the entire matrix.

Approach 1: Binary Search on Value Range (Time: O(m log(mn)), Space: O(1))

The key observation: the multiplication table is sorted both row-wise and column-wise. Instead of generating all values, search over the numeric range [1, m * n]. For a candidate value mid, count how many numbers in the table are ≤ mid. Each row i contributes min(n, mid / i) elements. Summing this for i = 1..m gives the count in O(m). If the count is smaller than k, move the search right; otherwise move left. This monotonic property makes binary search ideal. The approach avoids storing the table and directly pinpoints the kth value.

The counting step relies on simple division and iteration, making the method efficient even when m and n are up to 30,000. This technique is common in problems where the search space is numeric rather than index-based. The multiplication table structure combined with math reasoning enables fast counting.

Approach 2: Min Heap / Priority Queue (Time: O(k log m), Space: O(m))

Another way is to treat each row of the multiplication table as a sorted list: i, 2i, 3i, ... , ni. Insert the first element of each row (i * 1) into a min heap. Repeatedly pop the smallest element and push the next value from the same row (i * (j + 1)). After performing k extractions, the last popped value is the answer.

This technique mirrors the classic "merge k sorted lists" pattern. Each heap node stores the value along with its row index and column multiplier. While straightforward, it becomes slower when k is large because every step performs heap operations. Memory usage also grows with the number of rows pushed into the heap.

Recommended for interviews: Binary search on the value range is the expected solution. Interviewers want to see the insight that you can count how many numbers ≤ x without constructing the table. The heap approach demonstrates understanding of sorted structures, but the binary search method shows stronger algorithmic optimization.