Nearly everyone has used the Multiplication Table. The multiplication table of size m x n is an integer matrix mat where mat[i][j] == i * j (1-indexed).
Given three integers m, n, and k, return the kth smallest element in the m x n multiplication table.
Example 1:
Input: m = 3, n = 3, k = 5 Output: 3 Explanation: The 5th smallest number is 3.
Example 2:
Input: m = 2, n = 3, k = 6 Output: 6 Explanation: The 6th smallest number is 6.
Constraints:
1 <= m, n <= 3 * 1041 <= k <= m * nProblem 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.
The general idea is to use binary search to find the kth smallest element in the multiplication table. The key observation is that for a candidate number X, we can count how many numbers in the multiplication table are less than or equal to X, without constructing the entire table explicitly. Counting these numbers can be efficiently done by iterating over the rows and determining the highest multiple that does not exceed X.
This C solution implements the binary search technique to find the kth smallest number in the multiplication table. The function `countLessOrEqual` computes how many numbers are less than or equal to the given value x. In the main logic, binary search narrows down the potential candidates for the kth smallest number.
Time Complexity: O(m * log(m * n))
Space Complexity: O(1)
This approach uses a min-heap (priority queue) to keep track of the smallest unseen elements in the multiplication table. By continuously adding the next minimum elements from the rows, we can extract them in order until we reach the kth smallest element.
This C++ code uses a min-heap to track the smallest values efficiently. We insert initial multiples from each row into the heap and extract the smallest at each step, pushing the next element from the same row.
Time Complexity: O(k log m)
Space Complexity: O(m)
| Approach | Complexity |
|---|---|
| Binary Search Method | Time Complexity: O(m * log(m * n)) |
| Priority Queue (Heap) Method | Time Complexity: O(k log m) |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Binary Search on Value Range | O(m log(mn)) | O(1) | Best general solution for large tables. Avoids generating the matrix and scales well when m and n are large. |
| Min Heap / Priority Queue | O(k log m) | O(m) | Useful when k is relatively small or when applying the k-way merge pattern across sorted rows. |
668. Kth Smallest Number in Multiplication Table Leetcode Daily Challenge • Code with Alisha • 7,958 views views
Watch 9 more video solutions →Practice Kth Smallest Number in Multiplication Table with our built-in code editor and test cases.
Practice on FleetCode