• 37.8%

https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/#/description

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.

49ms, 85.38%, October 18, 2016

https://discuss.leetcode.com/topic/52865/my-solution-using-binary-search-in-c

My solution using Binary Search in C++

https://discuss.leetcode.com/topic/53126/o-n-from-paper-yes-o-rows

O(n) from paper. Yes, O(#rows).

It’s O(n) where n is the number of rows (and columns), not the number of elements. So it’s very efficient. The algorithm is from the paper Selection in X + Y and matrices with sorted rows and columns, which I first saw mentioned by @elmirap (thanks).

The basic idea: Consider the submatrix you get by removing every second row and every second column. This has about a quarter of the elements of the original matrix. And the k-th element (k-th smallest I mean) of the original matrix is roughly the (k/4)-th element of the submatrix. So roughly get the (k/4)-th element of the submatrix and then use that to find the k-th element of the original matrix in O(n) time. It’s recursive, going down to smaller and smaller submatrices until a trivial 2×2 matrix. For more details I suggest checking out the paper, the first half is easy to read and explains things well. Or @zhiqing_xiao’s solution+explanation.

Cool: It uses variants of saddleback search that you might know for example from the Search a 2D Matrix II problem. And it uses the median of medians algorithm for linear-time selection.

Optimization: If k is less than n, we only need to consider the top-left k×k matrix. Similar if k is almost n2. So it’s even O(min(n, k, n^2-k)), I just didn’t mention that in the title because I wanted to keep it simple and because those few very small or very large k are unlikely, most of the time k will be “medium” (and average n2/2).

Implementation: I implemented the submatrix by using an index list through which the actual matrix data gets accessed. If [0, 1, 2, …, n-1] is the index list of the original matrix, then [0, 2, 4, …] is the index list of the submatrix and [0, 4, 8, …] is the index list of the subsubmatrix and so on. This also covers the above optimization by starting with [0, 1, 2, …, k-1] when applicable.

Application: I believe it can be used to easily solve the Find K Pairs with Smallest Sums problem in time O(k) instead of O(k log n), which I think is the best posted so far. I might try that later if nobody beats me to it (if you do, let me know :-). Update: I did that now.

https://discuss.leetcode.com/topic/52947/c-priority-queue-solution-o-klogn

C++ priority queue solution O(klogn)

https://discuss.leetcode.com/topic/54262/c-o-n-time-o-n-space-solution-with-detail-intuitive-explanation

C++ O(n)-time O(n)-space solution with detail intuitive explanation

This thread is inspired by @StefanPochmann’s thread, which mentioned Mirzaian and Arjoandi’s paper.

Preparations

1. When n==1 (i.e. the matrix is 1x1. n is the number of row), the problem is trival. Hencefore we only consider the case n>=2.
Rather than finding one k-th element from the matrix, we will select TWO elements (say, k0-th element and k1-th element) simultaneously, such that 0<=k0<=k1 < n * n and k1-k0<=4n. Obviously, if we can complete the aforementioned selection in O(n), we can find the k-th element in O(n) by simply letting k=k0=k1.
2. Let x0 denote the k0-th element; let x1 denote the k1-th element. Obviously we have x0<=x1.
Now we will introduce how to select x0 and x1 in O(n).

General idea:

For an nxn matrix, where n is large, we try to select x0 and x1 in a recursive way.

1. (Determine submatrix) This step constructs one submatrix, whose number of elements will be approximately a quarter of the original matrix. The submatrix is defined as every other row and every other column of the original matrix. The last row and the last column are included too (the reason will be stated in the sequel.) Then the dimension of the matrix is approximately (n/2) x (n/2). The submatrix is recorded by the indices in the original matrix.

Example 1: the original matrix has indices {0, 1, 2, 3, 4}, then the submatrix has indices {0, 2, 4}.

Example 2: the original matrix has indices {0,1, 2, 3, 4, 5}, then the submatrix has indices {0, 2,4, 5}.

1. (Determine new k’s) This step determines two new k’s (denoted as k0_ and k1_) such that (i) k0_ is the largest possible integer to ensure k0_-th element in the new submatrix (denoted as x0_) is not greater than x0; (ii) k1_ is the smallest possible integer to ensure k1_-th element in the new submatrix (denoted as x1_) is not less than x1. This step is the most tricky step.

Picture: the way to determine k0_ and k1_: https://drive.google.com/open?id=0By2m48ItFbTeeDFvaS1WcV9qSWM

The picture can also be founded here.

Recall that we mentioned the last row and column shall always be included in the matrix. That is to ensure we can always found the x1_ such that x1_ >= x1.

1. (Call recursively) Obtainx0_ and x1_ by recursion.
2. (Partition) Partition all elements in the original nxn elements into three parts: P1={e: e < x0_}, P2={e: x0_ <= e < x1_ }, P3={e: x1_ < e}. We only need to record the cardinality of P1 and P2 (denoted as |P1| and |P2| respectively), and the elements in P2. Obviously, the cardinality of P2 is O(n).
3. (Get x0 and x1) From the definition of k0_ and k1_, we have |P1| < k0 <= |P1|+|P2|. When |P1| < k0 < |P1|+|P2|, x0 is the k0-|P1|-th element of P2; otherwise x0=x1_. x1 can be determined in a similar way. This action is also O(n).

Complexities:

• Time: O(n) —– Apply T(n) = T(n/2) + O(n) in the Master’s Theorem.
• Space: O(n)

C++ Accepted Code:

https://discuss.leetcode.com/topic/52886/c-solution-same-as-find-k-pairs-with-smaller-sums

C++ solution same as Find K pairs with smaller sums

https://discuss.leetcode.com/topic/52866/python-one-line-solution

python one-line solution …

life is too short to figure out more intelligent solution…

https://discuss.leetcode.com/topic/52912/binary-search-heap-and-sorting-comparison-with-concise-code-and-1-liners-python-72-ms

Binary Search, Heap and Sorting comparison, with concise code and 1-liners, Python 72 ms

For n X n matrix,

1. Binary search (based on the solution from @光速小子) gives me 72 ms.

The time complexity is O(n log(n) log(N)), where N is the search space that ranges from the smallest element to the biggest element. You can argue that int implies N = 2^32, so log(N) is constant. In a way, this is an O(n * log(n)) solution.

The space complexity is constant.

I thought this idea was weird for a while. Then I noticed the previous problem 377. Combination Sum IV is pretty much doing the same thing, so this idea may actually be intended.

Here is a 8-liner implementation:

1. Heap solution gives me 176 ms. The time complexity is O(k log n), so the worst-case and average-case time complexity is O(n^2 log n). Space complexity is O(n).
1. Sorting gives me 80ms. Time complexity of sorting an array of size n^2 is O(n^2 * log n). Space complexity is O(n^2).

The difference is that Timsort implemented in Python is capable of taking advantage of existing partial orderings. Moving sorted data in bulk is always faster than comparing and moving individual data elements, due to modern hardware architecture. Time complexity is the same because merging n sorted arrays of size n is still O(n^2 * log n) in the worst case.

Here are some O(n^3) (slow due to list concatenation) 1-liners:

and

Here are some O(n^2 * log n) 1-liners provided by @StefanPochmann

https://discuss.leetcode.com/topic/52862/share-my-python-solution-using-heap

Share My Python Solution using Heap

Algorithm

1. h: list of tuple (element, row, index), which is initialised with first element of each row in the matrix.
2. We maintain a heap. In the for loop, we get the smallest element v which is in row r, and replace v with the next element in the row r

Time Complexity

• insert an element into heap: O(log(n)), where n is the width of the matrix
• find k the k-th element O(k)
• Overall: O(klog(n))