# C++ Solution by Creating a Node Structure for heap

• 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;
pq.emplace(hn);
}
}

while(k-- && !pq.empty()){
HeapNode* node = pq.top();

res.emplace_back(make_pair(node->pr.first,node->pr.second));
pq.pop();
}

return res;
}``````

• 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{
public:
int x;
int y;
int sum;
Node(int x, int y, int sum): x(x), y(y), sum(sum){}
};

class Compare{
public:
bool operator() (Node n1, Node n2) {return n1.sum > n2.sum;}
};

class Solution {
public:
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;
}
};
``````

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