Show problems as
Classic problem #373MediumArrayHeap (Priority Queue)

Find K Pairs with Smallest Sums

Real-world version: Smallest Coupled Trims
Tracked in this browser only
Read Find K Pairs with Smallest Sums on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstTop K Frequent Elements · Priority Queues, animated step by step

A test rig couples one damper from the left tray with one damper from the right tray. Tray contents arrive as left and right, each a list of signed trim values in microns sorted in non-decreasing order. Trims may be negative.

A coupling picks one position in left and one position in right, and its coupled trim is the sum of the two values. Positions matter, not values: if a tray holds the same trim at two positions, each position gives its own coupling.

Return the k couplings whose coupled trim is smallest, each written as [left trim, right trim]. Order the answer by coupled trim ascending; where two couplings share a coupled trim, put the smaller left trim first, and if those match too, put the smaller right trim first. It is guaranteed that k does not exceed the number of couplings.

Examples

Example 1

Input
left = [-4,-1,0], right = [-2,3], k = 4
Output
[[-4,-2],[-1,-2],[0,-2],[-4,3]]

The listed couplings have coupled trims -6, -3, -2 and -1, which are the four smallest, and they appear in ascending order of coupled trim.

Example 2

Input
left = [1,3], right = [1,3], k = 3
Output
[[1,1],[1,3],[3,1]]

Coupled trims are 2, 4 and 4. The two couplings that share the trim 4 are ordered by their left trim, so 1 with 3 precedes 3 with 1.

Constraints

  • 1 <= left.length, right.length <= 10^5
  • -10^9 <= left[i], right[i] <= 10^9
  • left and right are both sorted in non-decreasing order.
  • 1 <= k <= 10^4
  • k <= left.length * right.length

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def smallest_coupled_trims(left: list[int], right: list[int], k: int) -> list[list[int]]:
Java
public List<List<Integer>> smallestCoupledTrims(int[] left, int[] right, int k)

More on the same topics