## 668. Kth Smallest Number in Multiplication Table

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.

Example 1:

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).


Example 2:

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).


Note:

1. The m and n will be in the range [1, 30000].
2. The k will be in the range [1, m * n]

b'
\n\n

## Solution

\n
\n

#### Approach #1: Brute Force [Memory Limit Exceeded]

\n

Intuition and Algorithm

\n

Create the multiplication table and sort it, then take the element.

\n\n

Complexity Analysis

\n
\n
• \n

Time Complexity: to create the table, and to sort it.

\n
• \n
• \n

Space Complexity: to store the table.

\n
• \n
\n
\n

#### Approach #2: Next Heap [Time Limit Exceeded]

\n

Intuition

\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

Algorithm

\n

Our heap is going to consist of elements , where is the next unused value of that row, and was the starting value of that row.

\n

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

Complexity Analysis

\n
\n
• \n

Time Complexity: . Our initial heapify operation is . Afterwards, each pop and push is , and our outer loop is \n

\n
• \n
• \n

Space Complexity: . Our heap is implemented as an array with elements.

\n
• \n
\n
\n

#### Approach #3: Binary Search [Accepted]

\n

Intuition

\n

As and are up to , linear solutions will not work. This motivates solutions with complexity, such as binary search.

\n

Algorithm

\n

Let\'s do the binary search for the answer .

\n

Say 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.

\n

Then (for our answer ), whenever , enough(x) is True; and whenever , enough(x) is False.

\n

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.

\n

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 .

\n\n

Complexity Analysis

\n
\n
• \n

Time Complexity: . Our binary search divides the interval into half at each step. At each step, we call enough which requires time.

\n
• \n
• \n

Space Complexity: . We only keep integers in memory during our intermediate calculations.

\n
• \n
\n
\n

Analysis written by: @awice

\n
'