Find K Pairs with Smallest Sums

Medium
972.

Find K Pairs with Smallest Sums

MediumArrayHeap (Priority Queue)AmazonGoogleLinkedInHotstar

Find K Pairs with Smallest Sums is a medium coding problem on arrays and heap, asked in Amazon, Google, LinkedIn and Hotstar interviews.

Two arrays sorted in non-decreasing order are given. A pair [u, v] takes one number from each.

Return the k pairs with the smallest sums, ordered by sum ascending; ties are broken by the smaller u, then the smaller v. If fewer than k pairs exist, return all of them.

Example 1

Input
nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Output
[[1,2],[1,4],[1,6]]

Example 2

Input
nums1 = [1,1,2], nums2 = [1,2,3], k = 2
Output
[[1,1],[1,1]]
Explanation
Both 1s in `nums1` pair with the 1 in `nums2`.

Example 3

Input
nums1 = [1,2], nums2 = [3], k = 3
Output
[[1,3],[2,3]]
Explanation
Only two pairs exist.

Constraints

  • 1 <= nums1.length, nums2.length <= 1000
  • -10^9 <= nums1[i], nums2[i] <= 10^9
  • nums1 and nums2 are sorted in non-decreasing order.
  • 1 <= k <= 1000
  • The pairs are returned sorted by sum, then by u, then by v.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @param {number} k
 * @return {number[][]}
 */
var kSmallestPairs = function(nums1, nums2, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find K Pairs with Smallest Sums — Problem & Solution

Find K Pairs with Smallest Sums solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Find K Pairs with Smallest Sums is a medium coding problem on arrays and heap, asked in Amazon, Google, LinkedIn and Hotstar interviews.

  • Difficulty: Medium
  • Topics: Arrays, Heap
  • Asked at: Amazon, Google, LinkedIn, Hotstar
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Two arrays sorted in non-decreasing order are given. A pair [u, v] takes one number from each.

Return the k pairs with the smallest sums, ordered by sum ascending; ties are broken by the smaller u, then the smaller v. If fewer than k pairs exist, return all of them.

Example 1

Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Output: [[1,2],[1,4],[1,6]]

Example 2

Input: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
Output: [[1,1],[1,1]]
Explanation: Both 1s in `nums1` pair with the 1 in `nums2`.

Example 3

Input: nums1 = [1,2], nums2 = [3], k = 3
Output: [[1,3],[2,3]]
Explanation: Only two pairs exist.

Constraints

  • 1 <= nums1.length, nums2.length <= 1000
  • -10^9 <= nums1[i], nums2[i] <= 10^9
  • nums1 and nums2 are sorted in non-decreasing order.
  • 1 <= k <= 1000
  • The pairs are returned sorted by sum, then by u, then by v.

Hints for Find K Pairs with Smallest Sums

  1. Hint 1

    Building all n × m pairs is far too many.

  2. Hint 2

    For a fixed i, the sums nums1[i] + nums2[j] increase with j, so only the frontier matters.

  3. Hint 3

    Seed a min-heap with [i, 0] for each i, and on popping [i, j] push [i, j + 1].

How to solve Find K Pairs with Smallest Sums

Keep a frontier of candidate pairs in a min-heap. Both arrays are sorted, so the next-smallest pair is always one step to the right of a pair already taken.

Approach

  1. Push [i, 0] for the first min(n, k) rows — no more can ever be needed.
  2. Pop the smallest, record [nums1[i], nums2[j]].
  3. Push [i, j + 1] if that column exists.
  4. Stop after k pops or when the heap empties.

Why it works

Only min(n, k) rows need seeding, because the answer can hold at most k pairs and each row contributes its smallest first. Ordering the heap on (sum, u, v) rather than the sum alone is what makes the output deterministic — without it, equal sums could come out in any order and two correct implementations would disagree.

Complexity

  • Time — O(k log k)
  • Space — O(k)

Pitfalls

  • Seeding every row is wasteful when n far exceeds k.
  • Pushing both [i+1, j] and [i, j+1] duplicates pairs unless visits are tracked.
  • Fewer than k pairs may exist; the loop must also stop on an empty heap.

Reference solution

Python

from typing import List
import heapq

def kSmallestPairs(nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
    n, m = len(nums1), len(nums2)
    heap = []
    for i in range(min(n, k)):
        heapq.heappush(heap, (nums1[i] + nums2[0], nums1[i], nums2[0], i, 0))
    out = []
    while len(out) < k and heap:
        _, u, v, i, j = heapq.heappop(heap)
        out.append([u, v])
        if j + 1 < m:
            heapq.heappush(heap, (nums1[i] + nums2[j + 1], nums1[i], nums2[j + 1], i, j + 1))
    return out

Java

public static int[][] kSmallestPairs(int[] nums1, int[] nums2, int k) {
    int n = nums1.length, m = nums2.length;
    PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> {
        long sa = (long) nums1[a[0]] + nums2[a[1]];
        long sb = (long) nums1[b[0]] + nums2[b[1]];
        if (sa != sb) return Long.compare(sa, sb);
        if (nums1[a[0]] != nums1[b[0]]) return Integer.compare(nums1[a[0]], nums1[b[0]]);
        return Integer.compare(nums2[a[1]], nums2[b[1]]);
    });
    int limit = Math.min(n, k);
    for (int i = 0; i < limit; i++) heap.add(new int[] { i, 0 });
    List<int[]> out = new ArrayList<>();
    while (out.size() < k && !heap.isEmpty()) {
        int[] cur = heap.poll();
        out.add(new int[] { nums1[cur[0]], nums2[cur[1]] });
        if (cur[1] + 1 < m) heap.add(new int[] { cur[0], cur[1] + 1 });
    }
    return out.toArray(new int[0][]);
}

C++

vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
    int n = (int) nums1.size(), m = (int) nums2.size();
    auto cmp = [&](const pair<int,int>& a, const pair<int,int>& b) {
        long long sa = (long long) nums1[a.first] + nums2[a.second];
        long long sb = (long long) nums1[b.first] + nums2[b.second];
        if (sa != sb) return sa > sb;
        if (nums1[a.first] != nums1[b.first]) return nums1[a.first] > nums1[b.first];
        return nums2[a.second] > nums2[b.second];
    };
    priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(cmp)> heap(cmp);
    int limit = min(n, k);
    for (int i = 0; i < limit; i++) heap.push({ i, 0 });
    vector<vector<int>> out;
    while ((int) out.size() < k && !heap.empty()) {
        auto cur = heap.top();
        heap.pop();
        out.push_back({ nums1[cur.first], nums2[cur.second] });
        if (cur.second + 1 < m) heap.push({ cur.first, cur.second + 1 });
    }
    return out;
}

JavaScript

var kSmallestPairs = function(nums1, nums2, k) {
    var n = nums1.length, m = nums2.length;
    var heap = [];
    var less = function(a, b) {
        var sa = nums1[a[0]] + nums2[a[1]], sb = nums1[b[0]] + nums2[b[1]];
        if (sa !== sb) return sa < sb;
        if (nums1[a[0]] !== nums1[b[0]]) return nums1[a[0]] < nums1[b[0]];
        return nums2[a[1]] < nums2[b[1]];
    };
    var push = function(v) {
        heap.push(v);
        var i = heap.length - 1;
        while (i > 0) {
            var p = (i - 1) >> 1;
            if (!less(heap[i], heap[p])) break;
            var t = heap[p]; heap[p] = heap[i]; heap[i] = t;
            i = p;
        }
    };
    var pop = function() {
        var top = heap[0];
        var last = heap.pop();
        if (heap.length > 0) {
            heap[0] = last;
            var i = 0;
            for (;;) {
                var l = 2 * i + 1, r = l + 1, s = i;
                if (l < heap.length && less(heap[l], heap[s])) s = l;
                if (r < heap.length && less(heap[r], heap[s])) s = r;
                if (s === i) break;
                var t = heap[s]; heap[s] = heap[i]; heap[i] = t;
                i = s;
            }
        }
        return top;
    };
    var limit = Math.min(n, k);
    for (var i2 = 0; i2 < limit; i2++) push([i2, 0]);
    var out = [];
    while (out.length < k && heap.length > 0) {
        var cur = pop();
        out.push([nums1[cur[0]], nums2[cur[1]]]);
        if (cur[1] + 1 < m) push([cur[0], cur[1] + 1]);
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Heaps and Priority Queues