Is Kth Smallest Number in Multiplication Table easy or hard?

LeetCode classifies this problem as Hard because the optimal solution requires recognizing binary search on the answer space. The implementation itself is relatively short, but identifying the counting strategy inside the multiplication table requires strong problem-solving insight.

Kth Smallest Number in Multiplication Table Python/Java solution

The binary search approach is language agnostic and easy to implement in Python, Java, C++, C#, C, or JavaScript. The algorithm repeatedly checks how many numbers are ≤ mid using division and adjusts the search bounds until the kth value is found.

How to solve Kth Smallest Number in Multiplication Table in O(m log(mn))?

Use binary search on the numeric range from 1 to m*n. For each mid value, count elements ≤ mid by summing min(n, mid / i) for every row i from 1 to m. If the count is smaller than k, move the search range right; otherwise move left. The smallest value that satisfies count ≥ k is the answer.

What is the best approach for Kth Smallest Number in Multiplication Table?

Binary search on the value range is the most efficient approach. Instead of generating the entire multiplication table, you binary search between 1 and m*n and count how many table values are ≤ mid. This counting step runs in O(m), giving an overall complexity of O(m log(mn)) with O(1) space.

Is Kth Smallest Number in Multiplication Table asked at Google/Amazon/Meta?

This problem represents a common interview pattern involving binary search on the answer space. Variants of this technique appear in interviews at companies such as Google, Amazon, and Meta, especially in questions about kth smallest elements in sorted structures or matrices.

What data structure is used in Kth Smallest Number in Multiplication Table?

The optimal approach mainly uses binary search with simple arithmetic counting, requiring no additional data structures. An alternative method uses a min heap (priority queue) to simulate merging sorted rows of the multiplication table.

What is the time complexity of Kth Smallest Number in Multiplication Table?

The optimal binary search solution runs in O(m log(mn)) time and O(1) space. Each binary search step counts how many numbers are ≤ mid by iterating through all rows and using division to determine valid column counts.

Description Solution Video 20:24

668. Kth Smallest Number in Multiplication Table

Hard55.1% acceptance5 companies

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

Asked at 5 companies

Medianet D. E. Shaw

Google Amazon Meta

Topics

Binary Search Math

20:24

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

668. Kth Smallest Number in Multiplication Table

Asked at 5 companies

Topics

Similar problems