Skip to main content

22. Find K Pairs with Smallest Sums

mediumAsked at Quora

Return the k pairs from two sorted arrays with the smallest sums — Quora uses this min-heap merge pattern to blend two ranked recommendation lists into a single top-K feed without sorting the full cross-product.

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

Problem

Given two integer arrays nums1 and nums2 sorted in non-decreasing order, and an integer k, return the k pairs (u, v) with the smallest sums u + v, where u is drawn from nums1 and v from nums2.

Constraints

  • 1 <= nums1.length, nums2.length <= 10^5
  • −10^9 <= nums1[i], nums2[i] <= 10^9
  • nums1 and nums2 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: All three smallest-sum pairs come from nums1[0] paired with each element of nums2.

Example 2

Input
nums1 = [1,1,2], nums2 = [1,2,3], k = 2
Output
[[1,1],[1,1]]

Approaches

1. Brute force — generate all pairs

Generate the full cross-product of pairs, sort by sum, return first k.

Time
O(m*n log(m*n))
Space
O(m*n)
function kSmallestPairs(nums1, nums2, k) {
  const pairs = [];
  for (const u of nums1)
    for (const v of nums2)
      pairs.push([u, v]);
  pairs.sort((a, b) => (a[0]+a[1]) - (b[0]+b[1]));
  return pairs.slice(0, k);
}

Tradeoff:

2. Min-heap (priority queue)

Seed the heap with (nums1[i], nums2[0]) for i in 0..min(k, m)-1. Each pop yields the current minimum pair; push the next candidate from nums2. Extract k times.

Time
O(k log k)
Space
O(k)
class MinHeap {
  constructor() { this.h = []; }
  push(item) {
    this.h.push(item);
    let i = this.h.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.h[p][0] <= this.h[i][0]) break;
      [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
      i = p;
    }
  }
  pop() {
    const top = this.h[0];
    const last = this.h.pop();
    if (this.h.length) {
      this.h[0] = last;
      let i = 0;
      while (true) {
        let s = i, l = 2*i+1, r = 2*i+2;
        if (l < this.h.length && this.h[l][0] < this.h[s][0]) s = l;
        if (r < this.h.length && this.h[r][0] < this.h[s][0]) s = r;
        if (s === i) break;
        [this.h[s], this.h[i]] = [this.h[i], this.h[s]];
        i = s;
      }
    }
    return top;
  }
  get size() { return this.h.length; }
}

function kSmallestPairs(nums1, nums2, k) {
  const heap = new MinHeap();
  const m = Math.min(nums1.length, k);
  for (let i = 0; i < m; i++)
    heap.push([nums1[i] + nums2[0], i, 0]);
  const result = [];
  while (result.length < k && heap.size) {
    const [, i, j] = heap.pop();
    result.push([nums1[i], nums2[j]]);
    if (j + 1 < nums2.length)
      heap.push([nums1[i] + nums2[j + 1], i, j + 1]);
  }
  return result;
}

Tradeoff:

Quora-specific tips

Quora asks this to evaluate whether you recognise the two-sorted-lists merge pattern from a disguised framing. The heap approach maps directly to their recommendation blending layer — know it cold, and call the pattern 'k-way merge' by name.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Find K Pairs with Smallest Sums and other Quora interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →