# Straight Forward O(min(klog(k), n^2)) solution using nth_element of C++

• The solution is straight forward. Put all 'possible' elements to another vector and use nth_element to that vector, which is linear time.

'possible' elements are those whose index i, j satisfies
i < k && i < matrix.size()
j < matrix.size() && (i + 1) * (j + 1) <= k

Note that for any k, for each i, there are at most [k / (i + 1)] 'possible' elements with on ith row. So there will be approximately klog(k) 'possible' elements totally. Also, number of 'possible' elements can be no more than n^2.

``````class Solution {
public:
int kthSmallest(vector<vector<int>>& matrix, int k) {
vector<int> m;
for(int i = 0; i < k && i < matrix.size(); ++i)
for(int j = 0; j < matrix.size() && (i + 1) * (j + 1) <= k; ++j)
m.push_back(matrix[i][j]);

nth_element(m.begin(), m.begin() + k - 1, m.end());
return *(m.begin() + k - 1);
}
};
``````

• seems "j < matrix.size()" is a typo of "j < matrix[0].size()"

• This post is deleted!

• @st.wanng No. The matrix is `n*n`, so it's not a typo.

• `nth_element` isn't O(n) but only average O(n).

• @StefanPochmann

There is worst case O(n) algorithm for doing nth_element anyway......

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.