How do you solve Find K Pairs with Smallest Sums on LeetCode?

Find K Pairs with Smallest Sums (LeetCode #373) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(k log k) time complexity and O(k) space complexity. Key insight: Using a min-heap allows us to efficiently find the smallest sums without generating all pairs.

What is the brute force solution for Find K Pairs with Smallest Sums?

The brute force approach for Find K Pairs with Smallest Sums is Brute Force, with O(n²) time complexity and O(n²) space complexity. The brute force approach generates all possible pairs from the two arrays and calculates their sums. It then sorts these pairs based on their sums and selects the first k pairs. The optimal Optimal Solution approach improves this to O(k log k).

What algorithm or data structure is used to solve Find K Pairs with Smallest Sums?

Find K Pairs with Smallest Sums uses the following concepts: Array, Heap (Priority Queue). The recommended patterns to study are: Heap, Array.

What are the interview tips for Find K Pairs with Smallest Sums?

Always clarify the constraints and edge cases before diving into the solution. Discuss your thought process and any potential optimizations with the interviewer. Practice explaining your code as you write it; this simulates the interview environment.

What are common mistakes when solving Find K Pairs with Smallest Sums?

Failing to consider the size of k relative to the number of possible pairs. Not using a priority queue correctly, leading to incorrect pair selection.

#373

Find K Pairs with Smallest Sums

Medium

ArrayHeap (Priority Queue)HeapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(k log k)
Space	O(n²)	O(k)

💡

Intuition

Time O(k log k)Space O(k)

Using a min-heap (priority queue) allows us to efficiently find the smallest pairs without generating all possible pairs. We start with the smallest elements and build up from there, ensuring we only explore promising pairs.

⚙️

Algorithm

4 steps

1Step 1: Initialize a min-heap and add the first pair (nums1[0], nums2[0]) along with its sum.
2Step 2: While we have pairs left in the heap and we need more pairs (k > 0), pop the smallest pair from the heap.
3Step 3: Add the next potential pairs from nums1 and nums2 to the heap, ensuring we only add pairs that haven't been added yet.
4Step 4: Decrement k and repeat until we have k pairs.

solution.py15 lines

1# Full working Python code
2import heapq
3
4def k_smallest_pairs(nums1, nums2, k):
5    min_heap = []
6    for i in range(min(k, len(nums1))):
7        heapq.heappush(min_heap, (nums1[i] + nums2[0], i, 0))
8    pairs = []
9    while k > 0 and min_heap:
10        sum_val, i, j = heapq.heappop(min_heap)
11        pairs.append([nums1[i], nums2[j]])
12        if j + 1 < len(nums2):
13            heapq.heappush(min_heap, (nums1[i] + nums2[j + 1], i, j + 1))
14        k -= 1
15    return pairs

ℹ

Complexity note: The time complexity is O(k log k) because we maintain a min-heap of size k, and each insertion and extraction operation takes O(log k). The space complexity is O(k) for storing the k pairs.

1Using a min-heap allows us to efficiently find the smallest sums without generating all pairs.
2Both input arrays are sorted, which helps in optimizing the pair generation.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.