Nearly every one have used the Multiplication Table. But could you find out the
k-th smallest number quickly from the multiplication table?
Given the height
m and the length
n of a
m * n Multiplication Table, and a positive integer
k, you need to return the
k-th smallest number in this table.
Input: m = 3, n = 3, k = 5 Output: Explanation: The Multiplication Table: 1 2 3 2 4 6 3 6 9 The 5-th smallest number is 3 (1, 2, 2, 3, 3).
Input: m = 2, n = 3, k = 6 Output: Explanation: The Multiplication Table: 1 2 3 2 4 6 The 6-th smallest number is 6 (1, 2, 2, 3, 4, 6).
nwill be in the range [1, 30000].
kwill be in the range [1, m * n]
Intuition and Algorithm\n
Create the multiplication table and sort it, then take the element.\n\n
Time Complexity: to create the table, and to sort it.\n
Space Complexity: to store the table.\n
Maintain a heap of the smallest unused element of each row. Then, finding the next element is a pop operation on the heap.\n
heap is going to consist of elements , where is the next unused value of that row, and was the starting value of that row.
We will repeatedly find the next lowest element in the table. To do this, we pop from the heap. Then, if there\'s a next lowest element in that row, we\'ll put that element back on the heap.\n\n
Time Complexity: . Our initial heapify operation is . Afterwards, each pop and push is , and our outer loop is \n\n
Space Complexity: . Our heap is implemented as an array with elements.\n
As and are up to , linear solutions will not work. This motivates solutions with complexity, such as binary search.\n
Let\'s do the binary search for the answer .\n
enough(x) is true if and only if there are or more values in the multiplication table that are less than or equal to . Colloquially,
enough describes whether is large enough to be the value in the multiplication table.
Then (for our answer ), whenever ,
True; and whenever ,
In our binary search, our loop invariant is
enough(hi) = True. At the beginning,
enough(m*n) = True, and whenever
hi is set, it is set to a value that is "enough" (
enough(mi) = True). That means
hi will be the lowest such value at the end of our binary search.
This leaves us with the task of counting how many values are less than or equal to . For each of rows, the row looks like . The largest possible that could appear is . However, if is really big, then perhaps , so in total there are values in that row that are less than or equal to .\n
After we have the count of how many values in the table are less than or equal to , by the definition of
enough(x), we want to know if that count is greater than or equal to .
Time Complexity: . Our binary search divides the interval into half at each step. At each step, we call
enough which requires time.
Space Complexity: . We only keep integers in memory during our intermediate calculations.\n
Analysis written by: @awice\n