Algorithm

Problem Name: 373. Find K Pairs with Smallest Sums

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 `(u1, v1), (u2, v2), ..., (uk, vk)` with the smallest sums.

Example 1:

```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:

```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:

```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 <= 105`
• `-109 <= nums1[i], nums2[i] <= 109`
• `nums1` and `nums2` both are sorted in ascending order.
• `1 <= k <= 104`

Code Examples

#1 Code Example with C Programming

```Code - C Programming```

``````
int** kSmallestPairs(int* nums1, int nums1Size, int* nums2, int nums2Size, int k, int** columnSizes, int* returnSize) {
int n, **p, *buff, x;
int i, j, l, r, c, *rn_on_col;  // current row number on each column
​
*returnSize = 0;
if (k  < = 0 || nums1Size == 0 || nums2Size == 0) return NULL;

n = nums1Size * nums2Size;
if (n > k) n = k;
p = malloc(n * sizeof(int *));
rn_on_col = malloc(nums2Size * sizeof(int));
// assert(p && rn_on_col);
memset(rn_on_col, -1, nums2Size * sizeof(int));

x = r = c = 0;
buff = malloc(2 * sizeof(int));
//assert(buff);
buff[0] = nums1[r];
buff[1] = nums2[c];
p[x ++] = buff;
rn_on_col[c] = r;
while (-- n) {
r = nums1Size - 1;
c = nums2Size - 1;
l = 0;
i = 1;
for (j = 0; j  <  nums2Size && i != 0; j ++) {
i = rn_on_col[j] + 1;
if (i  <  nums1Size &&
i != l &&
nums1[i] + nums2[j] < nums1[r] + nums2[c]) {
r = i; c = j;
}
l = i;
}
buff = malloc(2 * sizeof(int));
//assert(buff);
buff[0] = nums1[r];
buff[1] = nums2[c];
p[x ++] = buff;
rn_on_col[c] = r;
}

*returnSize = x;
*columnSizes = malloc(x * sizeof(int));
//assert(*columnSize);
for (i = 0; i  <  x; i ++) {
(*columnSizes)[i] = 2;
}

free(rn_on_col);

return p;
}
``````
Copy The Code &

Input

cmd
nums1 = [1,7,11], nums2 = [2,4,6], k = 3

Output

cmd
[[1,2],[1,4],[1,6]

#2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
auto comp = [](pair < int, int>& p1, pair<int, int>& p2){ return p1.first + p1.second > p2.first + p2.second; };
priority_queue < pair<int, int>, vector<pair<int, int>>, decltype(comp)>pq(comp);
for(auto x: nums1)
for(auto y: nums2) pq.push({x, y});
vector < pair<int, int>>res;
while(k-- && !pq.empty()) res.push_back(pq.top()), pq.pop();
return res;
}
};
``````
Copy The Code &

Input

cmd
nums1 = [1,7,11], nums2 = [2,4,6], k = 3

Output

cmd
[[1,2],[1,4],[1,6]

#3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
List<int[]> ans = new ArrayList<>();

if (nums1.length == 0 || nums2.length == 0 || k == 0) {
return ans;
}

PriorityQueue < Element> pq = new PriorityQueue<>(new Comparator() {
@Override
public int compare(Element o1, Element o2) {
return (o1.x + o1.y) - (o2.x + o2.y);
}
});

for (int i=0; i < nums2.length && i < k; i++) {
pq.offer(new Element(0, nums2[i], nums1[0]));
}

while (k-- > 0 && !pq.isEmpty()) {
Element temp = pq.poll();

if (temp.idx >= nums1.length-1) {
continue;
}

pq.offer(new Element(temp.idx+1, temp.x, nums1[temp.idx+1]));
}

return ans;
}

class Element {
int idx;
int x;
int y;

public Element(int val, int x, int y) {
this.idx = val;
this.x = x;
this.y = y;
}

@Override
public String toString() {
return "Element{" +
"idx=" + idx +
", x=" + x +
", y=" + y +
'}';
}
}
}
``````
Copy The Code &

Input

cmd
nums1 = [1,1,2], nums2 = [1,2,3], k = 2

Output

cmd
[[1,1],[1,1]]

#4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const kSmallestPairs = function (nums1, nums2, k) {
const pq = new PriorityQueue((a, b) => a[0] + a[1] < b[0] + b[1])
for(let i = 0; i  <  nums1.length && i < k; i++) {
pq.push([nums1[i], nums2[0], 0])
}
const res = []
while(k > 0 && !pq.isEmpty()) {
const [e1, e2, e2i] = pq.pop()
res.push([e1, e2])
if(e2i + 1 < nums2.length) pq.push([e1, nums2[e2i + 1], e2i + 1])
k--
}

return res
}

class PriorityQueue {
constructor(comparator = (a, b> => a > b) {
this.heap = []
this.top = 0
this.comparator = comparator
}
size() {
return this.heap.length
}
isEmpty() {
return this.size() === 0
}
peek() {
return this.heap[this.top]
}
push(...values) {
values.forEach((value) => {
this.heap.push(value)
this.siftUp()
})
return this.size()
}
pop() {
const poppedValue = this.peek()
const bottom = this.size() - 1
if (bottom > this.top) {
this.swap(this.top, bottom)
}
this.heap.pop()
this.siftDown()
return poppedValue
}
replace(value) {
const replacedValue = this.peek()
this.heap[this.top] = value
this.siftDown()
return replacedValue
}

parent = (i) => ((i + 1) >>> 1) - 1
left = (i) => (i << 1) + 1
right = (i) => (i + 1) << 1
greater = (i, j) => this.comparator(this.heap[i], this.heap[j])
swap = (i, j) => ([this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]])
siftUp = () => {
let node = this.size() - 1
while (node > this.top && this.greater(node, this.parent(node))) {
this.swap(node, this.parent(node))
node = this.parent(node)
}
}
siftDown = () => {
let node = this.top
while (
(this.left(node) < this.size() && this.greater(this.left(node), node)) ||
(this.right(node) < this.size() && this.greater(this.right(node), node))
) {
let maxChild =
this.right(node) < this.size() &&
this.greater(this.right(node), this.left(node))
? this.right(node)
: this.left(node)
this.swap(node, maxChild)
node = maxChild
}
}
}
``````
Copy The Code &

Input

cmd
nums1 = [1,1,2], nums2 = [1,2,3], k = 2

Output

cmd
[[1,1],[1,1]]

#5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def kSmallestPairs(self, nums1, nums2, k):
if not nums1 or not nums2: return []
n, res, cnt, heap = len(nums2), [], 0, [(nums1[i] + nums2[0], i, 0) for i in range(len(nums1))]
while heap and cnt < k:
cnt += 1
sm, i, j = heapq.heappop(heap)
res.append([nums1[i], nums2[j]])
if j + 1 < n: heapq.heappush(heap, (nums1[i] + nums2[j + 1], i, j + 1))
return res
``````
Copy The Code &

Input

cmd
nums1 = [1,2], nums2 = [3], k = 3

Output

cmd
[[1,3],[2,3]]