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 kth 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 kth 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 kth 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 kth 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 kth smallest number.

Learn more about Math and Binary Search patterns.

Solution Approach

The solution utilizes a binary search algorithm to efficiently find the kth 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 to 1 and right to m*n, covering the entire range of values in the multiplication table.
• While left is less than right, we calculate mid as the midpoint between left and right. In the provided code, the operation (left + right) >> 1 efficiently computes the midpoint by adding left and right 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 initialize cnt to 0 for this purpose.
• We then iterate over each row i from 1 to m. For each row, we increment cnt by min(mid // i, n). This gives us the total count of numbers not exceeding mid in the multiplication table.
• If cnt is at least k, it means we have at least k numbers in the multiplication table that are less than or equal to mid, and thus our kth smallest number is mid or lower. We then set our new right to mid.
• If cnt is less than k, it means we need a larger number to reach our target of k numbers less than or equal to it in the table. We then set our new left to mid + 1.
• This process is repeated, narrowing the search range until left and right converge, at which point left will have the value of the kth 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.

Example 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 kth 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.

1. We set left = 1 and right = 3*3 = 9.
2. Now we perform the binary search. We calculate mid by averaging left and right, so initially, mid would be (1 + 9) / 2 = 5.
3. 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 count cnt = 3 + 2 + 1 = 6.
4. Since cnt = 6 is greater than k = 5, we have more numbers than needed. Hence, right becomes mid = 5.
5. Repeat the binary search with left = 1 and right = 5. Our new mid is (1 + 5) / 2 = 3.
6. 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 of cnt = 3+1+1 = 5.
7. Since cnt = 5 is exactly k, we could settle for this mid. However, the binary search algorithm doesn't stop until left and right converge.
8. We don't update right since cnt is not greater than k. We would update left to mid + 1, which now equals 4.
9. Now left = 4 and right = 5. Since left is not less than right, the while loop terminates.
10. We have found our kth smallest number which is left = 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 kth 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

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.