Reference: LeetCode EPI 11.6

Difficulty: Medium

## Problem

Given a

`n x n`

matrix where each of the rows and columns are sorted in ascending order, find the`kth`

smallest element in the matrix.

Note that it is the

`kth`

smallest element in the sorted order, not the`kth`

distinct element.

**Note:** You may assume $k$ is always valid, $1 ≤ k ≤ n^2$.

**Example:**

1 | matrix = [ |

## Analysis

### Brute-Force

1 | // Brute-Force |

**Time:** $O(n^2\log{k})$**Space:** $O(k)$

### Row Heap

- Add the
`first row`

into the priority queue. Poll values from it for`k times`

then the last one we poll will be the kth smallest. - Each time we poll a value from it, we should
`offer`

its next value if available.

**Note:** We can also use the column.

1 | // PQ (min-heap) |

**Time:** $O(n\log{k})$**Space:** $O(k)$

If we use bottom-up heapification, it should be $O(n + k\log{n})$

If $k < n$, we can have pruning:

### Binary Search

Reference:

- Java Alternative Solution 2 with line-by-line comment
- Binary Search, Heap and Sorting comparison, with concise code and 1-liners, Python 72 ms
- Share my thoughts and Clean Java Code

The key point for any binary search is to figure out `search space`

. There are two kinds of search space: `index`

and `range`

. Usually, when the array is sorted in one direction, we can use `index`

as search space; otherwise, we use values as our search space.

In this case, we cannot use index as our search space, because the matrix is sorted in two directions, we can not find a linear way to map the number and its index.

1 | public int kthSmallest(int[][] matrix, int k) { |

**Time:** $O(n\log{n}\log{N})$

- $N$ is the search space that ranges from the smallest to the largest element.
- Each
`count`

takes $O(n\log{n})$ in the best case when`mid`

is getting smaller. - Each
`count`

takes $O(n^2)$ in the worst case when`mid`

is getting larger.

**Space:** $O(1)$

**Improvement:**

We can actually improve `count`

function.

**Time:** $O(n\log{N})$**Space:** $O(1)$

Count by `row`

starting from `up-right`

:

1 | // do a binary search |

Count by `column`

starting from `bottom-left`

:

1 | private int count(int[][] matrix, int mid) { |