Concise AC C++ solution using priority_queue

  • 0

    Just the same idea as the problem "find k pairs with smallest sums" using priority queue.

    class Solution {
        int kthSmallest(vector<vector<int>>& matrix, int k) {
            auto compare = [&matrix](pair<int, int> a, pair<int, int> b){
                return matrix[a.first][a.second] > matrix[b.first][b.second];
            priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(compare)> min_heap(compare);
            int m = matrix.size();
            int n = matrix[0].size();
            for(int i=0;i<m;i++)
                min_heap.emplace(i, 0);
            int res;
            for(int i=0;i<k;i++){
                auto temp =;
                res = matrix[temp.first][temp.second];
                if(temp.second < n-1)
                    min_heap.emplace(temp.first, temp.second+1);
            return res;

Log in to reply

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