> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Find K Pairs with Smallest Sums

> Tested Python solution for LeetCode 373 with 20 pytest cases. Generate a practice environment with lcpy.

LeetCode 373, [Medium](/catalog/medium). Topics: [Array](/catalog/topics/array), [Heap (Priority Queue)](/catalog/topics/heap-priority-queue). [View on LeetCode](https://leetcode.com/problems/find-k-pairs-with-smallest-sums/description/).

Generate this problem as a practice environment: tested reference solution, 20 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 373   # by problem number
lcpy gen -s find_k_pairs_with_smallest_sums   # by problem name
```

## Problem

You are given two integer arrays `nums1` and `nums2` sorted in **non-decreasing 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.

### Examples

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

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

### Constraints

* 1 \<= nums1.length, nums2.length \<= 10^5
* -10^9 \<= nums1\[i], nums2\[i] \<= 10^9
* nums1 and nums2 both are sorted in non-decreasing order.
* 1 \<= k \<= 10^4
* k \<= nums1.length \* nums2.length

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/find_k_pairs_with_smallest_sums/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/find_k_pairs_with_smallest_sums/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
import heapq


class Solution:
    # Time: O(k log min(k, len(nums1)))
    # Space: O(min(k, len(nums1)))
    def k_smallest_pairs(self, nums1: list[int], nums2: list[int], k: int) -> list[list[int]]:
        result: list[list[int]] = []
        heap: list[tuple[int, int, int]] = []
        for i in range(min(len(nums1), k)):
            heapq.heappush(heap, (nums1[i] + nums2[0], i, 0))
        while heap and len(result) < k:
            _, i, j = heapq.heappop(heap)
            result.append([nums1[i], nums2[j]])
            if j + 1 < len(nums2):
                heapq.heappush(heap, (nums1[i] + nums2[j + 1], i, j + 1))
        return result
```

## Complexity

| Time | Space |
| - | - |
| O(k log min(k, len(nums1))) | O(min(k, len(nums1))) |

## Tags


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.