Kth Smallest Number in Multiplication Table

HARD

Description

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 k^th smallest element in the m x n multiplication table.

Example 1:

Input: m = 3, n = 3, k = 5
Output: 3
Explanation: The 5^th smallest number is 3.

Example 2:

Input: m = 2, n = 3, k = 6
Output: 6
Explanation: The 6^th smallest number is 6.

Constraints:

1 <= m, n <= 3 * 10⁴
1 <= k <= m * n

Approaches

Checkout 3 different approaches to solve Kth Smallest Number in Multiplication Table. Click on different approaches to view the approach and algorithm in detail.

Brute Force: Generate and Sort

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 = 1 to m and the inner loop from j = 1 to n.
Inside the inner loop, calculate the product i * j and add it to the list.
After the loops complete, the list will contain all m * n elements.
Sort the list in ascending order.
The k-th smallest element is the element at index k - 1 of the sorted list.

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 Analysis

Time Complexity: 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 Complexity: 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.

Pros and Cons

Pros:

Very simple to understand and implement.
Correct for small values of m, n, and k.

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 Exceeded errors for the given constraints.

Code Solutions

Checking out 3 solutions in different languages for Kth Smallest Number in Multiplication Table. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Kth Smallest Number in Multiplication Table

Algorithms:

Binary Search

Patterns:

Math

Companies:

DE Shaw |