# C++ O(nlogn) easy to understand solution

• ok. we need to find k'th smallest item in the matrix.

1. use maltiset (that allows duplicates) with size of k
2. fill in k items in a sorted list (multiset)
3. if a new item is bigger than max in a multiset (last item) then skip it. Else insert new (it will go somewhere in the middle of multiset) and remove last (last wont be k'th smallest anymore)
4. skip entire row and all beyond if first item in a row is bigger than max in multiset. because all the rest items will be bigger anyway.
5. return last item from multiset
``````int kthSmallest(vector<vector<int>>& matrix, int k)
{
multiset<int> smallest;

for (int ndxRow=0; ndxRow<matrix.size(); ++ndxRow)
{
// if current item is bigger than max from multiset - skip entire row and all the followings
if (smallest.size() == k && matrix[ndxRow][0] > *(smallest.rbegin()))
break;

for (int ndxCol=0; ndxCol<matrix[ndxRow].size(); ++ndxCol)
{
// fill in the k items first
if (smallest.size() < k)
{
smallest.insert(matrix[ndxRow][ndxCol]);
}
else
{
// if item is bigger than max - skip the rest
if (matrix[ndxRow][ndxCol] > *(smallest.rbegin()))
{
break;
}
// insert only those that are lesser than the last in a set
else
{
smallest.insert(matrix[ndxRow][ndxCol]);

// now remove the last one to keep size = k
set<int>::iterator itLast = smallest.end();
--itLast;
smallest.erase(itLast);
}

}
}
}

return *(smallest.rbegin());
}
``````

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