373. Find K Pairs with Smallest Sums

The idea is to try every pair of nums1 and nums2. For each pairs, we maintain a maximum heap. The heap order is determined by the sum of pair.  So when the heap size is less than k, we push the new pair to the heap. When the heap size is k, then we need to check if the new pair's sum is less than the heap top pair. If so, we push the new pair into heap and pop out the heap top. In the end, we output all the pairs in the heap.

1:  class Solution {  
2:  struct mycompare {  
3:    bool operator()(pair<int, int> &p1, pair<int, int> &p2) {  
4:      return p1.first + p1.second < p2.first + p2.second;  
5:    }  
6:  };  
7:  public:  
8:    vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {  
9:      priority_queue<pair<int, int>, vector<pair<int, int>>, mycompare> pq;  
10:      vector<pair<int, int>> res;  
11:      for (int i = 0; i < nums1.size(); i++) {  
12:        for (int j = 0; j < nums2.size(); j++) {  
13:          if (pq.size() < k) {  
14:            pq.push(make_pair(nums1[i], nums2[j]));  
15:          } else if (nums1[i] + nums2[j] < pq.top().first + pq.top().second) {  
16:            pq.push(make_pair(nums1[i], nums2[j]));  
17:            pq.pop();  
18:          }  
19:        }  
20:      }  
21:      while (!pq.empty()) {  
22:        res.push_back(pq.top());  
23:        pq.pop();  
24:      }  
25:      return res;  
26:    }  
27:  };  

When I revisited the problem, I maintained a minimum heap and pushed all the pairs into the minimum heap and output the top k pairs. Obviously, it is wasting space as well time and easy to make mistake in line 18. The solution above is much better.

1:  class Solution {  
2:  private:  
3:    class compare {  
4:    public:  
5:      bool operator() (pair<int, int> &a, pair<int, int> &b) {  
6:        return a.first + a.second > b.first + b.second;  
7:      }  
8:    };  
9:  public:  
10:    vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {  
11:      priority_queue<pair<int, int>, vector<pair<int,int>>, compare> minHeap;  
12:      for (int i = 0; i < nums1.size(); i++) {  
13:        for (int j = 0; j < nums2.size(); j++) {  
14:          minHeap.push(make_pair(nums1[i], nums2[j]));  
15:        }  
16:      }  
17:      vector<pair<int, int>> res;  
18:      while (!minHeap.empty() && k) {  
19:        res.push_back(minHeap.top());  
20:        minHeap.pop();  
21:        k--;  
22:      }  
23:      return res;  
24:    }  
25:  };  

There is more efficient way mentioned by the top rated solution. Need to investigate later.