Find K Pairs with Smallest Sums

Solving tips

Picture the m×n sum grid; sorted inputs make every row and column non-decreasing, so run a best-first (Dijkstra-style) frontier instead of materializing it.
Seed a min-heap with (i, 0) for the first min(k, m) rows, then after popping (i, j) push only its right neighbor (i, j+1) — each row enters in order, so no visited set is needed.
Store indices (not just values) in the heap so you can advance rightward and keep index-distinct duplicate pairs separate.
Target O(k log k) time and O(k) space; stop when the heap empties to handle the 'fewer than k pairs' case.

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 off the table — the answer must cost roughly O(k log k).

Think about it first

Hint 1

Picture the m-by-n grid of sums `nums1[i] + nums2[j]`. Because both arrays are sorted, each row and each column of that grid is non-decreasing. Where must the overall smallest sum sit?

Hint 2

Once you take a pair `(i, j)`, which grid cells become newly "eligible" as candidates for the next-smallest sum? You never need to consider a cell before its left/up neighbor has been taken.

Hint 3

Min-heap frontier: seed with `(i, 0)` for the first `min(k, m)` rows. Pop the smallest sum, record it, and push only its right neighbor `(i, j + 1)`. Each row's cells enter in order, no visited-set needed, and you stop after k pops.

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


class Solution:
    def kSmallestPairs(self, 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 — hundreds of gigabytes before the sort even starts. The constraints exist precisely to kill this.

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.

The tidy 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


class Solution:
    def kSmallestPairs(self, 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.”

import heapq
from typing import List


class Solution:
    def kSmallestPairs(self, 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.