C++ Solution by Creating a Node Structure for heap

  • 1

    struct HeapNode{

        int sum;
        pair<int,int> pr;
    struct compare{
        bool operator()(HeapNode* hn1, HeapNode* hn2){
            return hn1->sum > hn2->sum;
    vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        vector<pair<int, int> > res;
         priority_queue<HeapNode*, vector<HeapNode*> , compare > pq;
        for(int i = 0; i < min(k,(int)nums1.size()); i++){
            for(int j  = 0; j < min(k,(int)nums2.size()); j++){
                int sum = nums1[i] + nums2[j];
                pair<int, int> pr;
                pr = make_pair(nums1[i],nums2[j]);
                HeapNode* hn = new HeapNode();
                hn->sum = sum;
                hn->pr = pr;
        while(k-- && !pq.empty()){
            HeapNode* node = pq.top();
        return res;

  • 0

    hey, bloomer,

    After being inspired by someone else, I implemented similar solution, but this solution may not go through matrix[nums1.size()-1][nums2.size()-1].

    class Node{
        int x;
        int y;
        int sum;
        Node(int x, int y, int sum): x(x), y(y), sum(sum){}
    class Compare{
        bool operator() (Node n1, Node n2) {return n1.sum > n2.sum;}
    class Solution {
        vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
            vector<pair<int, int>> ret;
            vector<vector<bool>> record(nums1.size(), vector<bool>(nums2.size(), true));
            priority_queue<Node, vector<Node>, Compare> min_heap;
            if (nums1.empty() || nums2.empty() || !k) return ret;
            min_heap.push(Node(0, 0,nums1[0]+nums2[0]));
            // get min and add candidates
            for (int i=1; i<=k; i++){
                if (min_heap.empty()) break;
                Node cur = min_heap.top(); min_heap.pop();
                ret.push_back(pair<int,int>(nums1[cur.x], nums2[cur.y]));
                if (cur.x+1<nums1.size() && record[cur.x+1][cur.y]) {
                    record[cur.x+1][cur.y] = false;
                    min_heap.push(Node(cur.x+1, cur.y, nums1[cur.x+1]+nums2[cur.y]));
                if (cur.y+1<nums2.size() && record[cur.x][cur.y+1]) {
                    record[cur.x][cur.y+1] = false;
                    min_heap.push(Node(cur.x, cur.y+1, nums1[cur.x]+nums2[cur.y+1]));
            return ret;

Log in to reply

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