C++ O(nlogn) easy to understand solution


  • 0
    S

    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
                        {
                            // add a new item
                            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());
        }
    

Log in to reply
 

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