Clean C++ priority_queue solution using iterators

  • 15

    Yes. The idea is just similar to Merge K Sorted List. Keep a priority queue of iterators/pointers which points to the current head of a row.

    class Solution {
        vector<int> smallestRange(vector<vector<int>>& nums) {
            typedef vector<int>::iterator vi;
            struct comp {
                bool operator()(pair<vi, vi> p1, pair<vi, vi> p2) {
                    return *p1.first > *p2.first;
            int lo = INT_MAX, hi = INT_MIN;
            priority_queue<pair<vi, vi>, vector<pair<vi, vi>>, comp> pq;
            for (auto &row : nums) {
                lo = min(lo, row[0]);
                hi = max(hi, row[0]);
                pq.push({row.begin(), row.end()});
            vector<int> ans = {lo, hi};
            while (true) {
                auto p =;
                if (p.first == p.second)
                lo = *;
                hi = max(hi, *p.first);
                if (hi - lo < ans[1] - ans[0])
                    ans = {lo, hi};
            return ans;

  • 1

    The method of using iterators is cool!

  • 0
    This post is deleted!

Log in to reply

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