Kth Smallest Number in Multiplication Table
HardPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
This is the most straightforward and intuitive approach. The idea is to physically construct the entire m x n multiplication table, store all its m * n values in a single list, sort this list, and then simply pick the k-th element from the sorted list.
Algorithm
- Create a list or an array to hold all the numbers from the multiplication table.
- Use nested loops, with the outer loop running from
i = 1tomand the inner loop fromj = 1ton. - Inside the inner loop, calculate the product
i * jand add it to the list. - After the loops complete, the list will contain all
m * nelements. - Sort the list in ascending order.
- The
k-th smallest element is the element at indexk - 1of the sorted list.
Walkthrough
We begin by initializing a dynamic array or list. We then iterate through each row i from 1 to m and each column j from 1 to n, computing the product i * j and adding it to our list. Once all m * n products are generated and stored, we use a standard sorting algorithm to arrange them in non-decreasing order. Finally, the element at index k - 1 (since lists are 0-indexed) is our desired k-th smallest number.
import java.util.ArrayList;import java.util.Collections;import java.util.List; class Solution { public int findKthNumber(int m, int n, int k) { List<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); }}Complexity
Time
O(m * n * log(m * n)) Generating the `m * n` elements takes O(m * n) time. Sorting these elements dominates the complexity, taking O(m * n * log(m * n)) time. This is too slow for the given constraints.
Space
O(m * n) We need to store all `m * n` elements of the table in a list. For `m, n` up to `3 * 10^4`, this would require storing up to `9 * 10^8` integers, which is not feasible.
Trade-offs
Pros
Very simple to understand and implement.
Correct for small values of
m,n, andk.
Cons
Extremely inefficient in terms of time complexity, making it too slow for large inputs.
Requires a large amount of memory to store the entire multiplication table, which can lead to
Memory Limit Exceedederrors for the given constraints.
A more optimized approach treats the multiplication table as m sorted lists (the rows). We can use a min-heap to efficiently find the k-th smallest element by merging these m sorted lists. This avoids generating and storing the entire table at once.
Algorithm
- Treat the multiplication table as
msorted rows. Thei-th row is[i*1, i*2, ..., i*n]. - Create a min-heap (PriorityQueue in Java) to find the smallest element among the current heads of these
mlists. - Initially, populate the heap with the first element from each of the
mrows. Each entry in the heap should store the value, its row index, and its column index, e.g.,{value, row, col}. - Repeat the following
ktimes:- Extract the minimum element
{val, r, c}from the heap. - If this is the
k-th extraction,valis the answer. - If the extracted element was not the last in its row (i.e.,
c < n), add the next element from that row,{r * (c + 1), r, c + 1}, to the heap.
- Extract the minimum element
Walkthrough
We can model this problem as finding the k-th smallest element in m sorted arrays. A min-heap is the perfect data structure for this. We initialize the heap with the first element of each row. Then, we repeatedly extract the minimum element from the heap. After extracting an element, we add the next element from the same row into the heap. We continue this process k times. The k-th element we extract is the solution.
To make it slightly more efficient, we can ensure the heap size is min(m, n) by swapping m and n if m > n.
import java.util.PriorityQueue; class Solution { public int findKthNumber(int m, int n, int k) { // Using a min-heap to merge m sorted lists (rows) // The heap stores {value, row_index, col_index} PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]); // Add the first element of each row to the heap for (int i = 1; i <= m; i++) { minHeap.offer(new int[]{i, i, 1}); // {value, row, col} } int result = -1; // Extract the minimum k times for (int count = 0; count < k; count++) { int[] current = minHeap.poll(); result = current[0]; int row = current[1]; int col = current[2]; // If there's a next element in the same row, add it to the heap if (col < n) { minHeap.offer(new int[]{row * (col + 1), row, col + 1}); } } return result; }}Complexity
Time
O(k * log(m)) We perform `k` extractions from the heap, and each operation (poll or offer) takes O(log m) time, where `m` is the size of the heap. If `k` is close to `m*n`, this is still too slow.
Space
O(m) or O(min(m, n)) The heap will store at most one element from each of the `m` rows. This is a significant improvement over O(m * n).
Trade-offs
Pros
Much more space-efficient than the brute-force approach.
Faster than brute-force, especially when
kis small.
Cons
The time complexity is proportional to
k, which can be as large asm * n. In such cases, this approach will be too slow and result in aTime Limit Exceedederror.
The most efficient solution uses binary search on the answer. The possible values for the k-th smallest number range from 1 to m * n. For any given number x in this range, we can efficiently determine how many elements in the multiplication table are less than or equal to x. This monotonic property allows us to binary search for the smallest x for which this count is at least k.
Algorithm
- The
k-th smallest number must lie in the range[1, m * n]. We can binary search for this number. - Set
low = 1andhigh = m * n. - While
low < high:- Calculate
mid = low + (high - low) / 2. - Count how many numbers in the multiplication table are less than or equal to
mid. Let's call thiscount. - The
countcan be calculated in O(m) time. For each rowi, the number of elements<= midismin(n, mid / i). Sum these values for all rows from 1 tom. - If
count < k, it meansmidis too small, and thek-th element must be larger. So, we search in the upper half:low = mid + 1. - If
count >= k, it meansmidcould be our answer, or the answer is even smaller. So, we search in the lower half:high = mid.
- Calculate
- The loop terminates when
low == high, which is the smallest numberxsuch that there are at leastkelements less than or equal tox. This is our answer.
Walkthrough
The key insight is that for a given value x, we can count the number of products i * j that are less than or equal to x without generating the table. For each row i, the elements are i, 2i, 3i, .... The number of these elements less than or equal to x is the largest j such that i * j <= x, which is j <= x / i. Since j cannot exceed n, the count for row i is min(n, x / i). Summing this over all m rows gives the total count.
This counting function allows us to use binary search. We search for a value mid in [1, m*n]. If the count of elements <= mid is less than k, our target must be larger, so we search in [mid + 1, high]. Otherwise, mid is a potential answer, and we try to find a smaller one in [low, mid]. The final result of the binary search is the k-th smallest number.
class Solution { public int findKthNumber(int m, int n, int k) { int low = 1; int high = m * n; while (low < high) { int mid = low + (high - low) / 2; int count = countLessOrEqual(mid, m, n); if (count < k) { low = mid + 1; } else { high = mid; } } return low; } // Helper function to count numbers less than or equal to x in the table private int countLessOrEqual(int x, int m, int n) { int count = 0; for (int i = 1; i <= m; i++) { // For each row i, the number of elements <= x is min(n, x / i) count += Math.min(n, x / i); } return count; }}Complexity
Time
O(m * log(m*n)) The binary search performs `log(m*n)` iterations. In each iteration, the `countLessOrEqual` function takes O(m) time. To be more precise, it's O(min(m, n) * log(m*n)) if we always iterate over the smaller dimension.
Space
O(1) This approach uses only a few variables to keep track of the binary search range, resulting in constant extra space.
Trade-offs
Pros
Highly efficient time complexity, suitable for the given large constraints.
Optimal space complexity as it doesn't require storing any large data structures.
Cons
The logic is more complex and less intuitive than the other approaches.
Requires a good understanding of binary search on an answer space.
Solutions
Solution
class Solution { public int findKthNumber ( int m , int n , int k ) { int left = 1 , right = m * n ; while ( left < right ) { int mid = ( left + right ) >>> 1 ; int cnt = 0 ; for ( int i = 1 ; i <= m ; ++ i ) { cnt += Math . min ( mid / i , n ); } if ( cnt >= k ) { right = mid ; } else { left = mid + 1 ; } } return left ; } }class Solution { public: int findKthNumber ( int m , int n , int k ) { int left = 1 , right = m * n ; while ( left < right ) { int mid = ( left + right ) >> 1 ; int cnt = 0 ; for ( int i = 1 ; i <= m ; ++ i ) cnt += min ( mid / i , n ); if ( cnt >= k ) right = mid ; else left = mid + 1 ; } return left ; } };class Solution : def findKthNumber ( self , m : int , n : int , k : int ) -> int : left , right = 1 , m * n while left < right : mid = ( left + right ) >> 1 cnt = 0 for i in range ( 1 , m + 1 ): cnt += min ( mid // i , n ) if cnt >= k : right = mid else : left = mid + 1 return leftVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.