# Kth Smallest Number in Multiplication Table
**Difficulty:** HARD
[External](https://leetcode.com/problems/kth-smallest-number-in-multiplication-table)
Canonical: https://scaleengineer.com/dsa/problems/kth-smallest-number-in-multiplication-table
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Companies:** [DE Shaw](https://scaleengineer.com/companies/de-shaw)
---
## Problem
Nearly everyone has used the [Multiplication Table](https://en.wikipedia.org/wiki/Multiplication%5Ftable). The multiplication table of size `m x n` is an integer matrix `mat` where `mat[i][j] == i * j` (**1-indexed**).

Given three integers `m`, `n`, and `k`, return _the_ `kth` _smallest element in the_ `m x n` _multiplication table_.

**Example 1:**

![](https://assets.glich.co/dsa/kth-smallest-number-in-multiplication-table/image0.jpg) 

**Input:** m = 3, n = 3, k = 5
**Output:** 3
**Explanation:** The 5th smallest number is 3.

**Example 2:**

![](https://assets.glich.co/dsa/kth-smallest-number-in-multiplication-table/image1.jpg) 

**Input:** m = 2, n = 3, k = 6
**Output:** 6
**Explanation:** The 6th smallest number is 6.

**Constraints:**

* `1 <= m, n <= 3 * 104`
* `1 <= k <= m * n`

# Approaches
## Brute Force: Generate and Sort
This is the most straightforward and intuitive approach. The idea is to physically construct the entire `m x n` multiplication table, store all its `m * n` values in a single list, sort this list, and then simply pick the `k`-th element from the sorted list.
**Time:** O(m * n * log(m * n))
Generating the `m * n` elements takes O(m * n) time. Sorting these elements dominates the complexity, taking O(m * n * log(m * n)) time. This is too slow for the given constraints. · **Space:** O(m * n)
We need to store all `m * n` elements of the table in a list. For `m, n` up to `3 * 10^4`, this would require storing up to `9 * 10^8` integers, which is not feasible.
**Pros:** Very simple to understand and implement.; Correct for small values of `m`, `n`, and `k`.
**Cons:** Extremely inefficient in terms of time complexity, making it too slow for large inputs.; Requires a large amount of memory to store the entire multiplication table, which can lead to `Memory Limit Exceeded` errors for the given constraints.
### Explanation
We begin by initializing a dynamic array or list. We then iterate through each row `i` from 1 to `m` and each column `j` from 1 to `n`, computing the product `i * j` and adding it to our list. Once all `m * n` products are generated and stored, we use a standard sorting algorithm to arrange them in non-decreasing order. Finally, the element at index `k - 1` (since lists are 0-indexed) is our desired `k`-th smallest number.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public int findKthNumber(int m, int n, int k) {
        List<Integer> table = new ArrayList<>();
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                table.add(i * j);
            }
        }
        Collections.sort(table);
        return table.get(k - 1);
    }
}
```
### Algorithm
- Create a list or an array to hold all the numbers from the multiplication table.
- Use nested loops, with the outer loop running from `i = 1` to `m` and the inner loop from `j = 1` to `n`.
- Inside the inner loop, calculate the product `i * j` and add it to the list.
- After the loops complete, the list will contain all `m * n` elements.
- Sort the list in ascending order.
- The `k`-th smallest element is the element at index `k - 1` of the sorted list.

## Using a Min-Heap (Priority Queue)
A more optimized approach treats the multiplication table as `m` sorted lists (the rows). We can use a min-heap to efficiently find the `k`-th smallest element by merging these `m` sorted lists. This avoids generating and storing the entire table at once.
**Time:** O(k * log(m))
We perform `k` extractions from the heap, and each operation (poll or offer) takes O(log m) time, where `m` is the size of the heap. If `k` is close to `m*n`, this is still too slow. · **Space:** O(m) or O(min(m, n))
The heap will store at most one element from each of the `m` rows. This is a significant improvement over O(m * n).
**Pros:** Much more space-efficient than the brute-force approach.; Faster than brute-force, especially when `k` is small.
**Cons:** The time complexity is proportional to `k`, which can be as large as `m * n`. In such cases, this approach will be too slow and result in a `Time Limit Exceeded` error.
### Explanation
We can model this problem as finding the `k`-th smallest element in `m` sorted arrays. A min-heap is the perfect data structure for this. We initialize the heap with the first element of each row. Then, we repeatedly extract the minimum element from the heap. After extracting an element, we add the next element from the same row into the heap. We continue this process `k` times. The `k`-th element we extract is the solution.

To make it slightly more efficient, we can ensure the heap size is `min(m, n)` by swapping `m` and `n` if `m > n`.

```java
import java.util.PriorityQueue;

class Solution {
    public int findKthNumber(int m, int n, int k) {
        // Using a min-heap to merge m sorted lists (rows)
        // The heap stores {value, row_index, col_index}
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);

        // Add the first element of each row to the heap
        for (int i = 1; i <= m; i++) {
            minHeap.offer(new int[]{i, i, 1}); // {value, row, col}
        }

        int result = -1;
        // Extract the minimum k times
        for (int count = 0; count < k; count++) {
            int[] current = minHeap.poll();
            result = current[0];
            int row = current[1];
            int col = current[2];

            // If there's a next element in the same row, add it to the heap
            if (col < n) {
                minHeap.offer(new int[]{row * (col + 1), row, col + 1});
            }
        }

        return result;
    }
}
```
### Algorithm
- Treat the multiplication table as `m` sorted rows. The `i`-th row is `[i*1, i*2, ..., i*n]`.
- Create a min-heap (PriorityQueue in Java) to find the smallest element among the current heads of these `m` lists.
- Initially, populate the heap with the first element from each of the `m` rows. Each entry in the heap should store the value, its row index, and its column index, e.g., `{value, row, col}`.
- Repeat the following `k` times:
  - Extract the minimum element `{val, r, c}` from the heap.
  - If this is the `k`-th extraction, `val` is the answer.
  - If the extracted element was not the last in its row (i.e., `c < n`), add the next element from that row, `{r * (c + 1), r, c + 1}`, to the heap.

## Binary Search on the Answer
The most efficient solution uses binary search on the answer. The possible values for the `k`-th smallest number range from `1` to `m * n`. For any given number `x` in this range, we can efficiently determine how many elements in the multiplication table are less than or equal to `x`. This monotonic property allows us to binary search for the smallest `x` for which this count is at least `k`.
**Time:** O(m * log(m*n))
The binary search performs `log(m*n)` iterations. In each iteration, the `countLessOrEqual` function takes O(m) time. To be more precise, it's O(min(m, n) * log(m*n)) if we always iterate over the smaller dimension. · **Space:** O(1)
This approach uses only a few variables to keep track of the binary search range, resulting in constant extra space.
**Pros:** Highly efficient time complexity, suitable for the given large constraints.; Optimal space complexity as it doesn't require storing any large data structures.
**Cons:** The logic is more complex and less intuitive than the other approaches.; Requires a good understanding of binary search on an answer space.
### Explanation
The key insight is that for a given value `x`, we can count the number of products `i * j` that are less than or equal to `x` without generating the table. For each row `i`, the elements are `i, 2i, 3i, ...`. The number of these elements less than or equal to `x` is the largest `j` such that `i * j <= x`, which is `j <= x / i`. Since `j` cannot exceed `n`, the count for row `i` is `min(n, x / i)`. Summing this over all `m` rows gives the total count.

This counting function allows us to use binary search. We search for a value `mid` in `[1, m*n]`. If the count of elements `<= mid` is less than `k`, our target must be larger, so we search in `[mid + 1, high]`. Otherwise, `mid` is a potential answer, and we try to find a smaller one in `[low, mid]`. The final result of the binary search is the `k`-th smallest number.

```java
class Solution {
    public int findKthNumber(int m, int n, int k) {
        int low = 1;
        int high = m * n;

        while (low < high) {
            int mid = low + (high - low) / 2;
            int count = countLessOrEqual(mid, m, n);

            if (count < k) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }

        return low;
    }

    // Helper function to count numbers less than or equal to x in the table
    private int countLessOrEqual(int x, int m, int n) {
        int count = 0;
        for (int i = 1; i <= m; i++) {
            // For each row i, the number of elements <= x is min(n, x / i)
            count += Math.min(n, x / i);
        }
        return count;
    }
}
```
### Algorithm
- The `k`-th smallest number must lie in the range `[1, m * n]`. We can binary search for this number.
- Set `low = 1` and `high = m * n`.
- While `low < high`:
  - Calculate `mid = low + (high - low) / 2`.
  - Count how many numbers in the multiplication table are less than or equal to `mid`. Let's call this `count`.
  - The `count` can be calculated in O(m) time. For each row `i`, the number of elements `<= mid` is `min(n, mid / i)`. Sum these values for all rows from 1 to `m`.
  - If `count < k`, it means `mid` is too small, and the `k`-th element must be larger. So, we search in the upper half: `low = mid + 1`.
  - If `count >= k`, it means `mid` could be our answer, or the answer is even smaller. So, we search in the lower half: `high = mid`.
- The loop terminates when `low == high`, which is the smallest number `x` such that there are at least `k` elements less than or equal to `x`. This is our answer.

# Solutions
### Java

```java
class Solution { public int findKthNumber ( int m , int n , int k ) { int left = 1 , right = m * n ; while ( left < right ) { int mid = ( left + right ) >>> 1 ; int cnt = 0 ; for ( int i = 1 ; i <= m ; ++ i ) { cnt += Math . min ( mid / i , n ); } if ( cnt >= k ) { right = mid ; } else { left = mid + 1 ; } } return left ; } }
```

### CPP

```cpp
class Solution { public: int findKthNumber ( int m , int n , int k ) { int left = 1 , right = m * n ; while ( left < right ) { int mid = ( left + right ) >> 1 ; int cnt = 0 ; for ( int i = 1 ; i <= m ; ++ i ) cnt += min ( mid / i , n ); if ( cnt >= k ) right = mid ; else left = mid + 1 ; } return left ; } };
```

### Python

```python
class Solution : def findKthNumber ( self , m : int , n : int , k : int ) -> int : left , right = 1 , m * n while left < right : mid = ( left + right ) >> 1 cnt = 0 for i in range ( 1 , m + 1 ): cnt += min ( mid // i , n ) if cnt >= k : right = mid else : left = mid + 1 return left
```