Kth Smallest Number in Multiplication Table - Video Solutions
668. Kth Smallest Number in Multiplication Table Leetcode Daily Challenge
Kth Smallest Number in Multiplication Table - Video Solution
Watch 10 video solutions for Kth Smallest Number in Multiplication Table, a hard level problem involving Math, Binary Search. This walkthrough by Code with Alisha has 8,231 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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 * n
Approach Overview
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.
Complexity Analysis
| 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. |