Skip to main content

373. Find K Pairs with Smallest Sums

medium

Given two sorted arrays, return the k pairs (one from each) with the smallest sums. A clean k-way merge variant — the heap holds candidate pairs ordered by sum.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

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 (u_1, v_1), (u_2, v_2), ..., (u_k, v_k) with the smallest sums.

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

Examples

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],[7,6],[11,2],[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].

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Brute force generates all n*m pairs, sorts, takes k. That's O(nm log(nm)) — too slow.

Hint 2

Observation: once you've picked pair (i, j), the next smallest must involve (i+1, j) or (i, j+1).

Hint 3

Treat this like a k-way merge: row i of an implicit matrix is nums2 added to nums1[i]. Each row is sorted.

Hint 4

Min-heap of (sum, i, j). Start by pushing (nums1[i]+nums2[0], i, 0) for the first few rows. Pop k times; each pop pushes (nums1[i]+nums2[j+1], i, j+1) if valid.

Solution approach

Reveal approach

Think of an implicit matrix M[i][j] = nums1[i] + nums2[j]. Each row is sorted, each column is sorted — a classic Young tableau. Use a min-heap of tuples (sum, i, j). Seed it with the first column: (nums1[i] + nums2[0], i, 0) for i in 0..min(k, len(nums1)). Pop k times: each pop yields the next-smallest pair, then push (nums1[i] + nums2[j+1], i, j+1) if j+1 is in range. Use a visited-set to avoid duplicate pushes, or seed only the first column to make it unnecessary (each row advances independently). O(k log k) time after the seed, O(k) extra space. The seed bound min(k, len(nums1)) matters: if k is small and n1 is huge, you don't want to push every row up front.

Complexity

Time
O(k log k)
Space
O(k)

Related patterns

  • heap
  • k-way-merge
  • two-heaps
  • matrix

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Meta
  • Microsoft

Practice these live with InterviewChamp.AI

Drill Find K Pairs with Smallest Sums and Heaps problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →