Scale Engineer

Find K Pairs with Smallest Sums

Med
#0360Time: O(N*M * log(N*M)), where N is the length of `nums1` and M is the length of `nums2`. Generating all pairs takes `O(N*M)` time. Sorting these `N*M` pairs takes `O(N*M * log(N*M))`, which dominates the complexity.Space: O(N*M) to store all the generated pairs in a list, where N and M are the lengths of `nums1` and `nums2` respectively.1 company
Data structures
ArrayHeap (Priority Queue)
Companies
LinkedIn

Prompt

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 (u1, v1), (u2, v2), ..., (uk, vk) with the smallest sums.

 

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

 

Constraints:

  • 1 <= nums1.length, nums2.length <= 105
  • -109 <= nums1[i], nums2[i] <= 109
  • nums1 and nums2 both are sorted in non-decreasing order.
  • 1 <= k <= 104
  • k <= nums1.length * nums2.length

Approaches

3 approaches with complexity analysis and trade-offs.

This approach involves generating every possible pair by combining one element from nums1 and one from nums2. After forming all pairs, they are sorted based on their sum in ascending order. Finally, the first k pairs from the sorted list are returned.

Algorithm

  • Create an empty list allPairs.
  • Iterate through each element u in nums1.
  • Inside this loop, iterate through each element v in nums2.
  • Create a pair (u, v) and add it to allPairs.
  • After generating all pairs, sort allPairs based on the sum of elements in each pair.
  • Create a result list and add the first k pairs from the sorted allPairs to it.
  • Return the result list.

Walkthrough

The algorithm iterates through nums1 with a nested loop for nums2. In the inner loop, a pair (nums1[i], nums2[j]) is formed and added to a list. This process continues until all nums1.length * nums2.length pairs are generated. The list of all pairs is then sorted using a custom comparator that compares the sums of the pairs. The sublist containing the first k elements is returned as the result.

import java.util.ArrayList;import java.util.Arrays;import java.util.Collections;import java.util.List; class Solution {    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {        List<List<Integer>> allPairs = new ArrayList<>();        for (int u : nums1) {            for (int v : nums2) {                allPairs.add(Arrays.asList(u, v));            }        }                // Sort the pairs based on their sum        Collections.sort(allPairs, (a, b) -> (a.get(0) + a.get(1)) - (b.get(0) + b.get(1)));                List<List<Integer>> result = new ArrayList<>();        for (int i = 0; i < Math.min(k, allPairs.size()); i++) {            result.add(allPairs.get(i));        }                return result;    }}

Complexity

Time

O(N*M * log(N*M)), where N is the length of `nums1` and M is the length of `nums2`. Generating all pairs takes `O(N*M)` time. Sorting these `N*M` pairs takes `O(N*M * log(N*M))`, which dominates the complexity.

Space

O(N*M) to store all the generated pairs in a list, where N and M are the lengths of `nums1` and `nums2` respectively.

Trade-offs

Pros

  • Very simple and straightforward to implement.

Cons

  • Highly inefficient for large inputs.

  • Will likely cause Time Limit Exceeded (TLE) and Memory Limit Exceeded (MLE) errors due to creating and sorting a potentially huge list of pairs.

Solutions

class Solution { public List < List < Integer >> kSmallestPairs ( int [] nums1 , int [] nums2 , int k ) { PriorityQueue < int []> q = new PriorityQueue <>( Comparator . comparingInt ( a -> a [ 0 ])); for ( int i = 0 ; i < Math . min ( nums1 . length , k ); ++ i ) { q . offer ( new int [] { nums1 [ i ] + nums2 [ 0 ], i , 0 }); } List < List < Integer >> ans = new ArrayList <>(); while (! q . isEmpty () && k > 0 ) { int [] e = q . poll (); ans . add ( Arrays . asList ( nums1 [ e [ 1 ]], nums2 [ e [ 2 ]])); -- k ; if ( e [ 2 ] + 1 < nums2 . length ) { q . offer ( new int [] { nums1 [ e [ 1 ]] + nums2 [ e [ 2 ] + 1 ], e [ 1 ], e [ 2 ] + 1 }); } } return ans ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem