O(Klog(N)) solution using priority queue.


  • 0
    T
    int kthSmallest(vector<vector<int>>& matrix, int k) {
            const int N = matrix.size();
            auto comp = [&matrix](const pair<int, int>& a, const 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(comp)> min_que(comp);
            for(int i=0; i<N; ++i) min_que.emplace(i, 0);
            while(--k){
                auto ctop = min_que.top();
                min_que.pop();
                if(ctop.second+1 < N) min_que.emplace(ctop.first, ctop.second+1);
            }
            auto rtop = min_que.top();
            return matrix[rtop.first][rtop.second];
        }

Log in to reply
 

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