Find K Pairs With Smallest Sums Problem


Description

LeetCode Problem 373.

You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k. Define a pair (u, v) which consists of one element from the first array and one element from the second array.

Return the k pairs (u_1, v_1), (u_2, v_2), …, (u_k, v_k) with the smallest sums.

Example 1:

1
2
3
Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Output: [[1,2],[1,4],[1,6]]
Explanation: The first 3 pairs are returned from the sequence: [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

Example 2:

1
2
3
Input: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
Output: [[1,1],[1,1]]
Explanation: The first 2 pairs are returned from the sequence: [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]

Example 3:

1
2
3
Input: nums1 = [1,2], nums2 = [3], k = 3
Output: [[1,3],[2,3]]
Explanation: All possible pairs are returned from the sequence: [1,3],[2,3]

Constraints:

  • 1 <= nums1.length, nums2.length <= 10^5
  • -10^9 <= nums1[i], nums2[i] <= 10^9
  • nums1 and nums2 both are sorted in ascending order.
  • 1 <= k <= 1000


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        vector<vector<int>> ans;
        priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>> > pq;
        
        if (nums1.empty() || nums2.empty())
            return ans;
        
        for (int i = 0; i < nums1.size(); i ++) {
            for (int j = 0; j < nums2.size(); j ++) {
                pq.push({nums1[i]+nums2[j], nums1[i], nums2[j]});
            }
        }
        
        while (!pq.empty() && k > 0) {
            k --;
            vector<int> temp;
            temp.push_back(pq.top()[1]);
            temp.push_back(pq.top()[2]);
            ans.push_back(temp);
            pq.pop();
        }
        
        return ans;
    }
};




Related Posts

K-Th Smallest Prime Fraction Problem

LeetCode 786. You are given a sorted integer array arr...

Course Schedule III Problem

LeetCode 630. There are n different online courses numbered from...

IPO Problem

LeetCode 502. Suppose LeetCode will start its IPO soon. In...

Sliding Window Median Problem

LeetCode 480. The median is the middle value in an...

Relative Ranks Problem

LeetCode 506. You are given an integer array score of...

Ugly Number II Problem

LeetCode 264. An ugly number is a positive integer whose...