{x}
blog image

Find K Pairs with Smallest Sums

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

Solution Explanation:

This problem asks to find the k pairs with the smallest sums from two sorted arrays, nums1 and nums2. A brute-force approach would generate all possible pairs and sort them, which is inefficient (O(nm log(nm)) time complexity). The optimal solution uses a min-heap to efficiently find the k smallest pairs.

Approach:

  1. Initialization: We create a min-heap. Initially, we add the pairs formed by the first element of nums1 and each element of nums2 (up to k pairs, to avoid unnecessary computation). Each element in the heap is a tuple: [sum, index_in_nums1, index_in_nums2]. This allows efficient tracking of the current pair and its constituent elements.

  2. Iteration: We repeatedly extract the minimum element (pair with the smallest sum) from the heap. This minimum pair is added to the result list.

  3. Heap Update: After extracting a pair [nums1[i], nums2[j]], we check if there's a next element in nums2 (i.e., j + 1 < len(nums2)). If so, we add the pair [nums1[i], nums2[j + 1]] to the heap to explore further possibilities using the same element from nums1. This is crucial for maintaining the minimum-sum property.

  4. Termination: The loop continues until we've collected k pairs or the heap is empty (meaning we've exhausted all possible pairs with sums less than or equal to the kth smallest sum).

Time Complexity Analysis:

  • Heap Initialization: O(min(k, m) log(min(k,m))), where 'm' is the length of nums1. This is due to adding at most k elements to the heap in the beginning.
  • Heap Operations: In each iteration, we perform heap pop (O(log k)) and potentially a heap push (O(log k)). We do this at most k times.
  • Overall: The dominant factor is the heap operations resulting in O(k log k) time complexity. If k is smaller than min(m,n), the overall time is dominated by heap operations and the complexity will be O(k log k). Otherwise if k is larger than min(m,n), the complexity will become O(min(m,n) log k).

Space Complexity Analysis:

The space complexity is O(k) due to the heap which holds at most k elements.

Code Explanation (Python):

The Python solution uses the heapq module for heap operations. The kSmallestPairs function follows the steps outlined above: initializing the heap, iterating to extract minimums, updating the heap, and collecting results.

Code Explanation (Java):

The Java solution uses PriorityQueue for the min-heap implementation. The Comparator is used to define the ordering within the heap based on the sum of pairs. The rest of the logic mirrors the Python version.

Code Explanation (C++):

The C++ solution uses priority_queue with a custom comparator lambda function to build the min-heap. The emplace method efficiently adds elements to the heap.

Code Explanation (Go):

The Go solution defines a custom heap (hp) using container/heap package, implementing the necessary Len, Less, Swap, Push, and Pop methods. The main logic again follows the same approach.