# 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.

Find 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]
```

## Thoughts

两个排好序的数组，从两个数组中分别选一个元素组成pair，返回前K个和最小的pair。思路类似ugly number。维持min heap，初始时先放入K个candidates，对于任意nums1\[0:K-1]内元素，把与它搭配最小的nums2\[0]放入。当把pair (nums1\[i], nums2\[j])从pq抛出并计入res后，nums1将它的下一个candidate(nums1\[i], nums2\[j +1])放入pq。

## Code

```python
from heapq import heappop, heappush

class Solution:
    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
        res, q = [], []
        if len(nums1) == 0 or len(nums2) == 0 or k == 0:
            return res
        for i in range(k):
            if i >= len(nums1):
                break
            heappush(q, (nums1[i] + nums2[0], nums1[i], 0))
        while k and q:
            cur = heappop(q)
            res.append([cur[1], cur[0] - cur[1]])
            k -= 1
            if cur[2] == len(nums2) - 1:
                continue
            heappush(q, (cur[1] + nums2[cur[2] + 1], cur[1], cur[2] + 1))
            
        return res
            
```

```java
class Solution {
    public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] + a[1] - b[0] - b[1]);
        List<int[]> res = new ArrayList<>();
        if (nums1.length == 0 || nums2.length == 0 || k == 0) {
            return res;
        }
        for (int i = 0; i < nums1.length; i++) {
            // 可能最小值的candidates, 和当前指向nums2的位置
            pq.offer(new int[]{nums1[i], nums2[0], 0});
        }

        for (int i = 0; i < k && !pq.isEmpty(); i++) {
            int[] min = pq.poll();
            res.add(new int[]{min[0], min[1]});
            if (min[2] == nums2.length - 1) {
                continue;
            }
            // 每次弹出一个就把它指向的下一个当作候选放入pq
            pq.offer(new int[]{min[0], nums2[min[2] + 1], min[2] + 1});
        }
        return res;
    }
}
```

## Analysis

时间复杂度O(klogn)

有没有办法可以优化呢？还可以，当k\<n时，我们实际上可以只初始化size为k的heap，因为nums1中排在k之后永远不会用到, 因为即使nums2中次大永远不被选到，k个都是在更换pair中的nums1，那最多也就到k，不会到nums1中k之后的。所以时间复杂度O(klgk).


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/heap/find-k-pairs-with-smallest-sums.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.