This is just yet another "Merge n sorted list" problem


  • 0
    P

    These two problems are equivalent.


  • 0
    P
    class Solution {
    public:
        int kthSmallest(vector<vector<int>>& matrix, int k) {
            auto compare = [](const pair<vector<int>*, size_t> vec1,
                              const pair<vector<int>*, size_t> vec2) {
                return vec1.first->at(vec1.second) > vec2.first->at(vec2.second);
            };
    
            vector<pair<vector<int>*, size_t>> heap;
    
            for (auto& row : matrix)
                heap.emplace_back(&row, 0);
    
            make_heap(heap.begin(), heap.end(), compare);
    
            int result = 0;
    
            while (k--) {
                auto top = heap.front();
    
                result = top.first->at(top.second);
    
                pop_heap(heap.begin(), heap.end(), compare);
                heap.pop_back();
    
                if (++top.second < top.first->size()) {
                    heap.push_back(move(top));
                    push_heap(heap.begin(), heap.end(), compare);
                }
            }
    
            return result;
        }
    };
    

Log in to reply
 

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