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.
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 ; } }Video 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.