668. Kth Smallest Number in Multiplication Table
Problem Description
In this problem, we are dealing with a multiplication table that is conceptualized as a 2D matrix with m
rows and n
columns. The value in each cell of the matrix is the product of its row and column indices (assuming 1-indexed, i.e., indexing starting from 1). For example, value at mat[i][j]
would be i * j
. The task is to find the k
th smallest element in this multiplication table.
To put it more concretely, if we flatten this table into a sorted single-dimensional array, we want to find the k
th element in that array. However, constructing this array explicitly would be inefficient, especially for large m
and n
, which is why we need a more clever approach to solve this problem.
Intuition
We use binary search to find the k
th smallest number in a more efficient way than sorting the entire multiplication table. Instead of constructing the multiplication table, we leverage its sorted properties indirectly.
The intuition is that every row in the multiplication table is a multiple of the first row. Given a number x
, we can easily calculate how many numbers in the table are less than or equal to x
by summing up the number of such elements in each row. This is because each row i
contains the multiples of i
up to i*n
, and each multiple less than or equal to x
counts towards our total. In other words, for each row i
, the number of elements that do not exceed x
is min(x // i, n)
.
We utilize binary search on the range of possible values – from 1 to m*n
which are all the possible values in the multiplication table. We look for the smallest number such that there are at least k
numbers less than or equal to it in the multiplication table. The key observation here is that if there are more than k
numbers less than or equal to a guess mid
in the table, then our answer must be less than or equal to mid
; otherwise, it must be greater.
By repeatedly narrowing our search range based on the count of elements up to the midpoint, we zero in on the k
th smallest number. When the left
and right
pointers in our binary search meet, we have found the least number for which there are k
or more numbers smaller or equal to it in the table, which by the properties of the search, will be exactly the k
th smallest number.
Learn more about Math and Binary Search patterns.
Solution Approach
The solution utilizes a binary search algorithm to efficiently find the k
th smallest number in the multiplication table. The binary search operates not on the multiplication table directly but on the value range from 1
to m*n
, which are the potential candidates for our answer. The midpoint of this range in each iteration gives us a guess to validate.
Here is a walk-through of the solution step by step:
- We initially set
left
to1
andright
tom*n
, covering the entire range of values in the multiplication table. - While
left
is less thanright
, we calculatemid
as the midpoint betweenleft
andright
. In the provided code, the operation(left + right) >> 1
efficiently computes the midpoint by addingleft
andright
together and then doing a right bitwise shift by 1 (which is equivalent to integer division by 2). - We need to count how many numbers in the table are less than or equal to
mid
. We initializecnt
to0
for this purpose. - We then iterate over each row
i
from1
tom
. For each row, we incrementcnt
bymin(mid // i, n)
. This gives us the total count of numbers not exceedingmid
in the multiplication table. - If
cnt
is at leastk
, it means we have at leastk
numbers in the multiplication table that are less than or equal tomid
, and thus ourk
th smallest number ismid
or lower. We then set our newright
tomid
. - If
cnt
is less thank
, it means we need a larger number to reach our target ofk
numbers less than or equal to it in the table. We then set our newleft
tomid + 1
. - This process is repeated, narrowing the search range until
left
andright
converge, at which pointleft
will have the value of thek
th smallest number in the multiplication table.
By repeatedly halving the search space, the binary search ensures an efficient approach with a time complexity of O(m * log(m*n)), which is much more efficient than generating the multiplication table and sorting it, especially for large values of m
and n
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with an example. Suppose we have a multiplication table with m = 3
rows and n = 3
columns, and we want to find the k
th smallest number in this table where k = 5
.
The multiplication table looks like this:
11 2 3 22 4 6 33 6 9
The flattened sorted version of this table would be [1, 2, 2, 3, 3, 4, 6, 6, 9]
, and clearly, the 5th number is 3
. But since we are not creating this array, let’s proceed with the binary search approach.
- We set
left
= 1 andright
= 3*3 = 9. - Now we perform the binary search. We calculate
mid
by averagingleft
andright
, so initially,mid
would be (1 + 9) / 2 = 5. - With
mid
= 5, we count the numbers less than or equal to 5 in the multiplication table. For the first row, all three numbers (1, 2, 3) are ≤ 5, so that's 3 counts. For the second row, two numbers (2, 4) are ≤ 5. For the third row, one number (3) is ≤ 5. So our countcnt
= 3 + 2 + 1 = 6. - Since
cnt
= 6 is greater thank
= 5, we have more numbers than needed. Hence,right
becomesmid
= 5. - Repeat the binary search with
left
= 1 andright
= 5. Our newmid
is (1 + 5) / 2 = 3. - With
mid
= 3, we count again. In all three rows, there's exactly one number less than or equal to 3. The counts are 3, 1 and 1, respectively, for a total ofcnt
= 3+1+1 = 5. - Since
cnt
= 5 is exactlyk
, we could settle for thismid
. However, the binary search algorithm doesn't stop untilleft
andright
converge. - We don't update
right
sincecnt
is not greater thank
. We would updateleft
tomid + 1
, which now equals 4. - Now
left
= 4 andright
= 5. Sinceleft
is not less thanright
, the while loop terminates. - We have found our
k
th smallest number which isleft
= 4.
However, we know from the hand-calculated array that the 5th smallest number is 3
, not 4
. This discrepancy is because the binary search approach narrows down to the number for which there are at least k
numbers smaller or equal to it in the table, and it doesn't stop until the left
boundary overtakes or meets the right
boundary, which implies that the left
boundary, in this case, may give us the first number that allows us to reach k
count, but not necessarily the k
th distinct number.
Thus, to correct the final output of our binary search case, we would instead take the right
boundary as our answer when the loop terminates, because it was the last number that gave us a count that was exactly k
before left
was incremented past it.
For our example, the 5th smallest number in the multiplication table is indeed 3
, which would be the correct final value of right
at the end of our binary search process.
Solution Implementation
1class Solution:
2 def findKthNumber(self, m: int, n: int, k: int) -> int:
3 # Initialize the search range between 1 and m*n
4 left, right = 1, m * n
5
6 # Binary search to find the k-th smallest number
7 while left < right:
8 mid = (left + right) // 2 # Use floor division for Python3
9 count = 0
10
11 # Count the number of values less than or equal to mid in the 2D multiplication table
12 for i in range(1, m + 1):
13 count += min(mid // i, n)
14
15 # If the count is greater than or equal to k, search the left half
16 if count >= k:
17 right = mid
18 # If the count is less than k, search the right half
19 else:
20 left = mid + 1
21
22 # The left pointer will be at the k-th smallest number after exiting the loop
23 return left
24
1class Solution {
2
3 /**
4 * Finds the kth smallest number in a multiplication table of size m x n.
5 *
6 * @param m The number of rows in the multiplication table.
7 * @param n The number of columns in the multiplication table.
8 * @param k The kth smallest number to find.
9 * @return The value of the kth smallest number in the multiplication table.
10 */
11 public int findKthNumber(int m, int n, int k) {
12 // Initialize the range of possible values for the kth number.
13 int left = 1; // The smallest number in the multiplication table.
14 int right = m * n; // The largest number in the multiplication table.
15
16 // Perform a binary search to find the kth number.
17 while (left < right) {
18 // Midpoint of the current search range.
19 int mid = left + (right - left) / 2;
20
21 // Counter for the number of elements less than or equal to mid.
22 int count = 0;
23
24 // Iterate through each row to count numbers less than or equal to mid.
25 for (int i = 1; i <= m; i++) {
26 // In row i, since the numbers are i, 2i, 3i, ..., ni,
27 // the count of numbers <= mid is min(mid / i, n).
28 count += Math.min(mid / i, n);
29 }
30
31 // Check if the count of numbers <= mid is at least k.
32 if (count >= k) {
33 // If there are at least k numbers <= mid, the kth number is
34 // in the left half of the search range.
35 right = mid;
36 } else {
37 // If there are fewer than k numbers <= mid, the kth number is
38 // in the right half of the search range.
39 left = mid + 1;
40 }
41 }
42
43 // The left pointer converges to the kth smallest number.
44 return left;
45 }
46}
47
1class Solution {
2public:
3 int findKthNumber(int m, int n, int k) {
4 // Initialize the binary search boundaries.
5 int left = 1, right = m * n;
6
7 // Execute the binary search.
8 while (left < right) {
9 // Calculate the middle point of the search space.
10 int mid = left + (right - left) / 2;
11 int count = 0; // This will hold the count of numbers less than or equal to 'mid'.
12
13 // Count how many numbers are less than or equal to 'mid' for each row.
14 for (int i = 1; i <= m; ++i) {
15 // In the i-th row, numbers are i, 2i, 3i, ..., ni.
16 // We determine how many of them are less than or equal to 'mid' by dividing 'mid' by i.
17 // However, the count cannot exceed 'n' (the number of columns).
18 count += std::min(mid / i, n);
19 }
20
21 // If the count is at least 'k', the desired value is at 'mid' or to the left of 'mid'.
22 if (count >= k) {
23 right = mid; // Narrow the search to the left half.
24 } else {
25 // If count is less than 'k', the desired value is to the right of 'mid'.
26 left = mid + 1; // Narrow the search to the right half.
27 }
28 }
29
30 // 'left' is now equal to the desired k-th number.
31 return left;
32 }
33};
34
1function findKthNumber(m: number, n: number, k: number): number {
2 // Initialize the binary search boundaries.
3 let left = 1;
4 let right = m * n;
5
6 // Execute the binary search.
7 while (left < right) {
8 // Calculate the middle point of the search space.
9 let mid = left + Math.floor((right - left) / 2);
10 let count = 0; // This will hold the count of numbers less than or equal to 'mid'.
11
12 // Count how many numbers are less than or equal to 'mid' for each row.
13 for (let i = 1; i <= m; ++i) {
14 // In the i-th row, numbers are i, 2i, 3i, ..., ni.
15 // We determine how many of them are less than or equal to 'mid' by dividing 'mid' by i.
16 // However, the count cannot exceed 'n' (the number of columns).
17 count += Math.min(Math.floor(mid / i), n);
18 }
19
20 // If the count is at least 'k', the desired value is at 'mid' or to the left of 'mid'.
21 if (count >= k) {
22 right = mid; // Narrow the search to the left half.
23 } else {
24 // If the count is less than 'k', the desired value is to the right of 'mid'.
25 left = mid + 1; // Narrow the search to the right half.
26 }
27 }
28
29 // 'left' is now equal to the desired k-th number.
30 return left;
31}
32
Time and Space Complexity
Time Complexity
The time complexity of the given code hinges on the binary search algorithm and the loop that calculates the count within each iteration. The binary search runs in O(log(m*n))
time, as it is applied to a range from 1 to m*n
. For each middle point mid
, we run a loop from 1 to m
, which results in a time complexity of O(m)
for that segment of the code. Therefore, the total time complexity of the algorithm, which is a combination of these two operations, is O(m * log(m*n))
.
Space Complexity
The space complexity of the code is O(1)
. This is because we only use a constant amount of additional space, namely variables for left
, right
, mid
, and cnt
, regardless of the size of the input parameters m
, n
, and k
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.