#373

Medium

auto_awesomeArray plus Heap (Priority Queue)

LeetCode Problem Workspace

Find K Pairs with Smallest Sums

Find K Pairs with Smallest Sums combines arrays and heap usage to select the smallest sum pairs efficiently.

Problem Statement

You are given two integer arrays, nums1 and nums2, sorted in non-decreasing order, along with an integer k. A pair consists of one element from nums1 and one element from nums2. Your goal is to return the k pairs with the smallest sums.

The problem is designed to test your ability to use heaps (priority queues) effectively while combining them with array operations. The challenge is in selecting pairs without exceeding the time complexity limits, especially when k is large.

Examples

Example 1

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

Output: [[1,2],[1,4],[1,6]]

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]]

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 Approach

Initial Pair Generation

Start by pairing the smallest elements of nums1 and nums2, which are the most likely candidates for the smallest sums. Begin by inserting the first few elements of the arrays into a min-heap (priority queue).

Heap-based Pair Extraction

Extract the pair with the smallest sum from the heap, and then push the next potential pair (next element in nums1 or nums2) into the heap. This process continues until k pairs are extracted or the heap is exhausted.

Optimizing Pair Selection

Avoid brute force enumeration of all pairs. Instead, take advantage of the sorted order of nums1 and nums2 to efficiently generate and select only the smallest sum pairs by using the heap to manage state transitions.

Complexity Analysis

Metric	Value
Time	O(\min(k \cdot \log k, m \cdot n \cdot \log (m \cdot n)))
Space	O(\min(k, m \cdot n))

The time complexity is O(min(k * log k, m * n * log (m * n))), where k is the number of pairs to find, and m and n are the lengths of nums1 and nums2 respectively. The space complexity is O(min(k, m * n)) due to the heap size and storage requirements.

What Interviewers Usually Probe

Can the candidate efficiently combine array traversal with heap operations?
How well does the candidate manage the heap size and limit unnecessary operations?
Does the candidate understand the trade-off between time and space complexity in heap-based solutions?

Common Pitfalls or Variants

Common pitfalls

Overpopulating the heap with all possible pairs instead of strategically pushing only potential candidates.
Incorrectly handling the heap extraction order or failing to manage heap transitions between pairs.
Failing to account for the sorted nature of the arrays, which can optimize the pairing strategy.

Follow-up variants

What if the arrays are unsorted? This would require sorting the arrays first before applying the heap method.
What if k exceeds the possible pairs from the arrays? In such cases, ensure the solution handles this scenario gracefully by limiting the output to the available pairs.
Handling arrays with duplicate elements. The solution should still work and return the correct k smallest sums, regardless of duplicates.

FAQ

What is the pattern for solving Find K Pairs with Smallest Sums?

The primary pattern involves using arrays in conjunction with a heap (priority queue) to efficiently select the k smallest sum pairs from the two sorted arrays.

How does the sorted order of nums1 and nums2 affect the solution?

The sorted order allows for efficient pair generation and prioritization of smaller sums in the heap, making the solution optimal in both time and space.

What is the time complexity of this solution?

The time complexity is O(min(k * log k, m * n * log (m * n))), where k is the number of pairs to find, and m and n are the lengths of the arrays.

How does the heap (priority queue) work in this problem?

The heap is used to efficiently manage the smallest sum pairs by always extracting the smallest pair and pushing the next viable pair into the heap.

What are the common mistakes when solving this problem?

Common mistakes include overpopulating the heap with all pairs, mismanaging heap transitions, or ignoring the sorted order of arrays for optimization.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def kSmallestPairs(
        self, nums1: List[int], nums2: List[int], k: int
    ) -> List[List[int]]:
        q = [[u + nums2[0], i, 0] for i, u in enumerate(nums1[:k])]
        heapify(q)
        ans = []
        while q and k > 0:
            _, i, j = heappop(q)
            ans.append([nums1[i], nums2[j]])
            k -= 1
            if j + 1 < len(nums2):
                heappush(q, [nums1[i] + nums2[j + 1], i, j + 1])
        return ans

Continue Practicing

#378 kth smallest element in a sorted matrix #347 top k frequent elements #407 trapping rain water ii