Find K Pairs With Smallest Sums · Interview Problem

Back to problems

Leetcode

Medium

Arrays

Heaps

Ordered Structures

Amazon

Google

Microsoft

Find K Pairs With Smallest Sums

Return the $k$ pairs formed from two sorted arrays that have the smallest sums.

Acceptance 50%

Start Practice

Problem Statement

Problem

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

Form pairs (u, v) where u comes from nums1 and v comes from nums2. Your task is to return the k pairs with the smallest sums u + v.

If fewer than k pairs exist, return all of them.

Notes

A pair is represented as [u, v].
If multiple pairs have the same sum, any valid order is acceptable unless otherwise stated.
The arrays are already sorted, which is an important part of the problem.

Input Format

Input

nums1: a sorted integer array
nums2: a sorted integer array
k: an integer

Output Format

Output

Return a list of up to k pairs [u, v] with the smallest sums.

Constraints

1 <= nums1.length, nums2.length
k >= 1
Arrays are sorted in non-decreasing order
If k exceeds the total number of possible pairs, return all pairs

Examples

Sample cases returned by the problem API.

Example 1

Input

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

Output

[[1,2],[1,4],[1,6]]

Explanation

The three smallest pair sums are 3, 5, and 7, produced by pairs [1,2], [1,4], and [1,6].

Example 2

Input

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

Output

[[1,1],[1,1]]

Explanation

The smallest sums are both 2, coming from the two distinct pairs that use the first two 1s from nums1 with 1 from nums2.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress