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);
}
};
```