This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

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 = 5Output: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 = 6Output:Explanation:The Multiplication Table: 1 2 3 2 4 6 The 6-th smallest number is 6 (1, 2, 2, 3, 4, 6).

**Note:**

- The
`m`

and`n`

will be in the range [1, 30000]. - The
`k`

will be in the range [1, m * n]

b'

\n## Solution

\n

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

\n

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

\n

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

\n

\n

'
\n\n

\n\n

**Intuition and Algorithm**

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

\n\n**Complexity Analysis**

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

\n \n - \n
Space Complexity: to store the table.

\n \n

\n

**Intuition**

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**

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.

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

**Intuition**

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

\n**Algorithm**

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

\nSay `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 , `enough(x)`

is `True`

; and whenever , `enough(x)`

is `False`

.

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 .

\nAfter 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 .

**Complexity Analysis**

- \n
- \n
Time Complexity: . Our binary search divides the interval into half at each step. At each step, we call

\n`enough`

which requires time. \n - \n
Space Complexity: . We only keep integers in memory during our intermediate calculations.

\n \n

\n

Analysis written by: @awice

\n