#668

Hard

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Kth Smallest Number in Multiplication Table

Find the kth smallest number in an m x n multiplication table using binary search over the valid answer space.

Problem Statement

The multiplication table of size m x n is an integer matrix mat where mat[i][j] == i * j (1-indexed). Given integers m, n, and k, your task is to find the kth smallest number in the m x n multiplication table.

Since the multiplication table is sorted row by row and column by column, finding the kth smallest element can be efficiently approached using binary search on the range of possible values in the table, leveraging the table's inherent structure to optimize the search.

Examples

Example 1

Input: m = 3, n = 3, k = 5

Output: 3

The 5th smallest number is 3.

Example 2

Input: m = 2, n = 3, k = 6

Output: 6

The 6th smallest number is 6.

Constraints

1 <= m, n <= 3 * 104
1 <= k <= m * n

Solution Approach

Binary Search on Answer Space

Start with binary search over the valid answer space. The smallest number is 1, and the largest is m * n. For each mid value in this range, count how many numbers in the table are less than or equal to mid. If the count is greater than or equal to k, adjust the search to the left half; otherwise, move the search to the right half.

Count the Elements Less Than or Equal to mid

For each mid value, iterate through the rows, counting how many elements are smaller than or equal to mid. Since the table is sorted, the number of elements less than or equal to a value in each row can be determined by a simple formula, which reduces the complexity of the counting operation.

Optimization by Early Termination

Once binary search narrows down the possible values to find the kth smallest number, further refinement can be done quickly. Early termination is possible when the binary search range has been minimized, reducing unnecessary computations.

Complexity Analysis

Metric	Value
Time	O(m * \log (m*n))
Space	O(1)

The time complexity is O(m * log(m * n)) because we perform binary search over the range [1, m * n] and for each mid, we count how many numbers are less than or equal to mid, which takes O(m) time. The space complexity is O(1), as we only need a constant amount of extra space aside from the input variables.

What Interviewers Usually Probe

The candidate should focus on utilizing binary search over the answer space effectively.
Expect the candidate to leverage the properties of the multiplication table to count elements efficiently in each row.
Look for an understanding of how to minimize unnecessary calculations through early termination or efficient counting.

Common Pitfalls or Variants

Common pitfalls

A common mistake is performing a brute force search, where the candidate tries to generate the entire multiplication table to find the kth smallest number. This approach is inefficient and fails for large inputs.
Misunderstanding how to count elements less than or equal to a mid value in each row of the multiplication table can lead to incorrect results or inefficient solutions.
Candidates may miss the optimal space complexity, leading to an unnecessarily large space usage.

Follow-up variants

What if the multiplication table is much larger? How would the solution scale with larger m and n?
Can the problem be solved without using binary search? If so, what trade-offs would be involved?
How can this approach be applied if the table is not sorted or if the rows and columns are not strictly increasing?

FAQ

How do I find the kth smallest number in the multiplication table?

Use binary search on the answer space, counting how many elements are smaller than or equal to the current mid value. Adjust the search range accordingly until you find the kth smallest element.

What is the time complexity of solving this problem?

The time complexity is O(m * log(m * n)) due to binary search over the range [1, m * n] and counting elements less than or equal to mid in each row, which takes O(m).

Can I solve the Kth Smallest Number in Multiplication Table without binary search?

While it's theoretically possible to use brute force or other methods, binary search is the most efficient approach for this problem, especially for larger values of m and n.

How does binary search help in this problem?

Binary search optimizes the search for the kth smallest element by reducing the answer space progressively, making the solution more efficient than brute force methods.

What are the constraints of the Kth Smallest Number in Multiplication Table problem?

The constraints are 1 <= m, n <= 3 * 10^4 and 1 <= k <= m * n, meaning that the solution must be efficient enough to handle large input sizes.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

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 left

Continue Practicing

#633 sum of square numbers #710 random pick with blacklist #754 reach a number