Find K Pairs with Smallest Sums

Problem

You are given two integer arrays nums1 and nums2, both sorted in non-decreasing order, and an integer k.

A pair is one element from each array: (u, v) with u from nums1 and v from nums2. Different index positions count as different pairs even if the values repeat.

Return the k pairs with the smallest sums u + v, as a list of [u, v] pairs. If fewer than k pairs exist in total, return them all. Any order among equal sums is accepted.

Examples

• nums1 = [1, 7, 11], nums2 = [2, 4, 6], k = 3 → [[1, 2], [1, 4], [1, 6]] — sums 3, 5, 7 beat every pair starting with 7 or 11.
• nums1 = [1, 1, 2], nums2 = [1, 2, 3], k = 2 → [[1, 1], [1, 1]] — the two 1s in nums1 each form their own pair with nums2’s first 1 (sums 2 and 2).
• nums1 = [1, 2], nums2 = [3], k = 10 → [[1, 3], [2, 3]] — only 2 pairs exist, so return both.

Constraints

• 1 <= len(nums1), len(nums2) <= 10^5
• -10^9 <= nums1[i], nums2[i] <= 10^9
• Both arrays sorted ascending
• 1 <= k <= 10^4

With up to 10^10 total pairs, enumerating them all is infeasible; the target is roughly O(k log k).

Think about it first

TL;DR

Min-heap frontier over the sorted sum-grid: O(k log k) time, O(k) space.

Approach 1 — Brute force (enumerate all pairs)

Generate every (u, v) pair, sort by sum, keep the first k.

from typing import List


def kSmallestPairs(nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
    pairs = [[u, v] for u in nums1 for v in nums2]
    pairs.sort(key=sum)
    return pairs[:k]

O(mn log(mn)) time and O(mn) space. With m = n = 10^5 that’s 10^10 pairs, far too many to materialize before the sort even starts. The constraints rule this out.

Approach 2 — Min-heap over the candidate frontier

The insight: view the sums as an m×n grid G[i][j] = nums1[i] + nums2[j]. Sorted inputs make every row and column non-decreasing, so G[i][j] can only be the next-smallest after its up-neighbor and left-neighbor are already taken. We can therefore walk the grid like a best-first search (Dijkstra-style frontier): keep a min-heap of candidate cells, always pop the smallest, and only then reveal its neighbors.

This version pushes one candidate per row: seed (i, 0) for the first min(k, m) rows (a pair in row i can never be in the answer before that row’s first column), and after popping (i, j) push only (i, j + 1). Each row feeds the heap left-to-right, so no cell is pushed twice and no visited-set is needed.

import heapq
from typing import List


def kSmallestPairs(nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
    heap = [
        (nums1[i] + nums2[0], i, 0)
        for i in range(min(k, len(nums1)))
    ]
    heapq.heapify(heap)

    result: List[List[int]] = []
    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

Walkthrough of nums1 = [1, 7, 11], nums2 = [2, 4, 6], k = 3:

• Seed rows 0..2: heap = {(3, 0,0), (9, 1,0), (13, 2,0)}.
• Pop (3, 0,0) → answer [1, 2]; push (5, 0,1). Heap {5, 9, 13}.
• Pop (5, 0,1) → answer [1, 4]; push (7, 0,2). Heap {7, 9, 13}.
• Pop (7, 0,2) → answer [1, 6]; row 0 exhausted, nothing pushed.
• 3 pairs collected → return [[1, 2], [1, 4], [1, 6]]. ✓

And for the duplicate case nums1 = [1, 1, 2], nums2 = [1, 2, 3], k = 2: seed {(2, 0,0), (2, 1,0), (3, 2,0)} — the two index-distinct (1, 1) pairs are separate heap entries, so the answer is [[1, 1], [1, 1]] as required.

Complexity: heap size never exceeds min(k, m); we do k pops and ≤ k pushes → O(k log k) time (plus O(min(k, m)) to seed), O(min(k, m)) space. Note tuple comparison falls back to the i, j ints on sum ties — all comparable, no crash.

Approach 3 — Two-neighbor BFS with a visited set (the general grid version)

The insight: the same frontier idea works without the per-row trick: start from cell (0, 0) only, and when popping (i, j) push both neighbors (i+1, j) and (i, j+1), using a visited set to avoid double-pushing a cell reachable two ways. This is the version that generalizes to “k-th smallest in a sorted matrix.”

Each cell unlocks its right and down neighbors, so the cells form a DAG. Cell (1, 1) is reachable from both (0, 1) and (1, 0), which is exactly why the visited set is needed:

graph LR
    A["(0,0)"] --> B["(0,1)"]
    A --> C["(1,0)"]
    B --> D["(0,2)"]
    B --> E["(1,1)"]
    C --> E
    C --> F["(2,0)"]

import heapq
from typing import List


def kSmallestPairs(nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
    m, n = len(nums1), len(nums2)
    heap = [(nums1[0] + nums2[0], 0, 0)]
    seen = {(0, 0)}
    result: List[List[int]] = []
    while heap and len(result) < k:
        _, i, j = heapq.heappop(heap)
        result.append([nums1[i], nums2[j]])
        if i + 1 < m and (i + 1, j) not in seen:
            seen.add((i + 1, j))
            heapq.heappush(heap, (nums1[i + 1] + nums2[j], i + 1, j))
        if j + 1 < n and (i, j + 1) not in seen:
            seen.add((i, j + 1))
            heapq.heappush(heap, (nums1[i] + nums2[j + 1], i, j + 1))
    return result

Tracing the first example: pop (3, 0,0) → push (9, 1,0) and (5, 0,1); pop (5, 0,1) → push (11, 1,1) and (7, 0,2); pop (7, 0,2) → three pairs collected, same answer as before. Each pop adds ≤ 2 cells, so the heap holds O(k) entries → O(k log k) time, O(k) space for heap plus visited set. Same asymptotics as Approach 2 but with the extra set bookkeeping — know both; interviewers ask for the visited-set variant when the data is a matrix rather than two arrays.

Common pitfalls

• Seeding all m rows instead of min(k, m) — with m = 10^5 and k = 10, you’d heapify 10^5 entries to output 10 pairs.
• Pushing both neighbors without a visited set: cell (i, j) gets pushed once via (i−1, j) and once via (i, j−1), duplicating answers.
• Storing pairs of values in the heap without indices — you lose the ability to find “the next element to the right,” and duplicated values collapse index-distinct pairs.
• Forgetting the “fewer than k pairs exist” case: the loop must stop when the heap empties, not assume k pops always succeed.

Pattern takeaway

When the candidate space is a grid (or any DAG) whose sums are monotone along each axis, don’t materialize it — run best-first search: heap of frontier candidates, pop the min, push only the cells that popping just unlocked. The heap stays O(k)-sized and total work is O(k log k), independent of the mn cells you never looked at. The per-row seeding trick removes the visited-set whenever one axis can be enumerated in order.