LeetCode 373: Find K Pairs with Smallest Sums Solution in Python – A Step-by-Step Guide

What Is LeetCode 373: Find K Pairs with Smallest Sums?

LeetCode 373: Find K Pairs with Smallest Sums provides two sorted integer arrays, nums1 and nums2, and an integer k. Your task is to return the k pairs (u, v) where u is from nums1 and v is from nums2, such that their sums (u + v) are the k smallest possible. It’s a problem that tests your ability to efficiently select from a large set of possibilities!

Problem Statement

• Input:
• nums1: Sorted list of integers (ascending).
• nums2: Sorted list of integers (ascending).
• k: Integer representing the number of pairs to return.
• Output: List[List[int]] - k pairs with the smallest sums.
• Rules:
• Each pair (u, v) has u from nums1, v from nums2.
• Return pairs in any order, as long as they’re the k smallest sums.

Constraints

• 1 <= nums1.length, nums2.length <= 10⁵
• -10⁹ <= nums1[i], nums2[i] <= 10⁹
• 1 <= k <= min(1000, nums1.length * nums2.length)
• nums1 and nums2 are sorted in ascending order.

Examples

• Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
• Output: [[1,2],[1,4],[1,6]]
• Possible sums: 3(1+2), 5(1+4), 7(1+6), 9(7+2), 11(7+4), 13(7+6), 13(11+2), 15(11+4), 17(11+6).
• Smallest 3: 3, 5, 7 → [[1,2], [1,4], [1,6]].
• Input: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
• Output: [[1,1],[1,1]]
• Sums: 2(1+1), 2(1+1), 3(1+2), 3(1+2), 3(2+1), 4(2+2), 5(2+3).
• Smallest 2: 2, 2 → [[1,1], [1,1]].
• Input: nums1 = [1,2], nums2 = [3], k = 3
• Output: [[1,3],[2,3]]
• Sums: 4(1+3), 5(2+3), only 2 pairs possible.

These show the pairing puzzle—let’s solve it!

Understanding the Problem: Finding K Smallest Pairs

To tackle LeetCode 373 in Python, we need to: 1. Generate pairs (u, v) from nums1 and nums2. 2. Compute their sums (u + v). 3. Select the k pairs with the smallest sums.

A naive approach might compute all sums and sort, but that’s inefficient. Instead, we’ll use:

• Best Solution: Min-heap—O(k log k) time, O(k) space—fast and optimized.
• Alternative Solution: Brute force—O(m*n log (m*n)) time, O(m*n) space—simple but slow.

Let’s optimize with the best solution!

Best Solution: Min-Heap

Why This Is the Best Solution

The min-heap approach runs in O(k log k) time by maintaining a priority queue of pairs, starting with the smallest possible sum and expanding only as needed. It leverages the sorted nature of the input arrays to avoid generating all m*n pairs—making it the most efficient solution for this problem!

How It Works

Think of it like a priority line:

• Heap: Use a min-heap with (sum, i, j) where sum = nums1[i] + nums2[j], i and j are indices.
• Start: Push (nums1[0] + nums2[0], 0, 0).
• Expand: Pop smallest sum, add pair, push next pairs (i+1, j) and (i, j+1) if valid, track seen pairs.
• Repeat: k times to get k smallest sums.
• Result: List of k pairs.

It’s like picking the next smallest pair smartly!

Step-by-Step Example

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

• Init: Heap = [(3, 0, 0)] (1+2), Seen = {(0,0)}, Result = [].
• Step 1:
• Pop (3, 0, 0), Result = [[1,2]].
• Push (5, 0, 1) (1+4), (9, 1, 0) (7+2).
• Heap = [(5, 0, 1), (9, 1, 0)], Seen = {(0,0), (0,1), (1,0)}.
• Step 2:
• Pop (5, 0, 1), Result = [[1,2], [1,4]].
• Push (7, 0, 2) (1+6), (11, 1, 1) (7+4).
• Heap = [(7, 0, 2), (9, 1, 0), (11, 1, 1)].
• Step 3:
• Pop (7, 0, 2), Result = [[1,2], [1,4], [1,6]].
• Push (13, 1, 2) (7+6), (0,2 not added, out of bounds).
• Heap = [(9, 1, 0), (11, 1, 1), (13, 1, 2)].
• Result: [[1,2], [1,4], [1,6]] (sums 3, 5, 7).

For nums1 = [1,1,2], nums2 = [1,2,3], k = 2:

• Init: Heap = [(2, 0, 0)], Result = [].
• Step 1: Pop (2, 0, 0), Result = [[1,1]], Heap = [(2, 0, 1), (3, 1, 0)].
• Step 2: Pop (2, 0, 1), Result = [[1,1], [1,2]], Heap = [(3, 0, 2), (3, 1, 0)].
• Result: [[1,1], [1,2]] (both sum to 2).

Code with Explanation

Here’s the Python code using a min-heap:

Copy codefrom heapq import heappush, heappop

class Solution:
    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
        if not nums1 or not nums2:
            return []

        # Min-heap: (sum, i, j) where i is index in nums1, j in nums2
        heap = []
        seen = set()
        result = []

        # Start with smallest pair
        heappush(heap, (nums1[0] + nums2[0], 0, 0))
        seen.add((0, 0))

        # Get k smallest pairs
        while heap and len(result) < k:
            curr_sum, i, j = heappop(heap)
            result.append([nums1[i], nums2[j]])

            # Add next possible pairs
            if i + 1 < len(nums1) and (i + 1, j) not in seen:
                heappush(heap, (nums1[i + 1] + nums2[j], i + 1, j))
                seen.add((i + 1, j))
            if j + 1 < len(nums2) and (i, j + 1) not in seen:
                heappush(heap, (nums1[i] + nums2[j + 1], i, j + 1))
                seen.add((i, j + 1))

        return result

Explanation

• Lines 5-7: Handle empty input cases.
• Lines 9-10: heap: Min-heap of (sum, i, j), seen: Track visited pairs.
• Lines 13-14: Push initial pair (nums1[0] + nums2[0], 0, 0).
• Lines 16-25: Main loop:
• Pop smallest sum, add pair to result.
• Push (i+1, j) and (i, j+1) if valid and unseen.
• Repeat k times or until heap is empty.
• Time: O(k log k)—k heap operations, log k for heap size.
• Space: O(k)—heap and seen set store up to k pairs.

This is like a smart pair picker—grab the smallest sums efficiently!

Alternative Solution: Brute Force

Why an Alternative Approach?

The brute force solution runs in O(mn log (mn)) time by generating all possible pairs, computing their sums, and sorting to pick the k smallest. It’s slower and uses more space—great for small inputs or understanding the full scope!

How It Works

• Generate: Create all m*n pairs.
• Sort: Sort by sum.
• Select: Take first k pairs.

Step-by-Step Example

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

• Pairs:
• (1,2)=3, (1,4)=5, (1,6)=7, (7,2)=9, (7,4)=11, (7,6)=13, (11,2)=13, (11,4)=15, (11,6)=17.
• Sort: [3, 5, 7, 9, 11, 13, 13, 15, 17].
• Take k=3: [3, 5, 7] → [[1,2], [1,4], [1,6]].

Code with Explanation

Copy codeclass Solution:
    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
        if not nums1 or not nums2:
            return []

        # Generate all pairs
        pairs = []
        for i in range(len(nums1)):
            for j in range(len(nums2)):
                pairs.append([nums1[i], nums2[j]])

        # Sort by sum
        pairs.sort(key=lambda x: x[0] + x[1])

        # Return k smallest
        return pairs[:min(k, len(pairs))]

Explanation

• Lines 6-10: Generate all pairs (u, v) in a list.
• Line 12: Sort pairs by sum using a lambda function.
• Line 14: Return first k pairs (or all if fewer).
• Time: O(m*n log (m*n))—sorting dominates.
• Space: O(m*n)—stores all pairs.

It’s like listing everything and picking the best—simple but heavy!

Comparing the Two Solutions

• Min-Heap (Best):
• Time: O(k log k)—heap ops.
• Space: O(k)—heap size.
• Pros: Fast, space-efficient.
• Cons: Heap logic less intuitive.
• Brute Force (Alternative):
• Time: O(m*n log (m*n))—sort all pairs.
• Space: O(m*n)—all pairs.
• Pros: Easy to code.
• Cons: Slow, memory-intensive.

Min-heap wins for efficiency!

Additional Examples and Edge Cases

• nums1=[1], nums2=[1], k=1: [[1,1]].
• nums1=[1,2], nums2=[], k=1: [].
• Large k: Min-heap scales better.

Both work, min-heap is faster.

Complexity Breakdown

• Min-Heap:
• Time: O(k log k).
• Space: O(k).
• Brute Force:
• Time: O(m*n log (m*n)).
• Space: O(m*n).

Min-heap excels for performance.

Key Takeaways

• Min-Heap: Pick smartly—fast and lean!
• Brute Force: List all—clear but slow!
• Pairs: Optimization is key.
• Python Tip: Heapq rocks—see [Python Basics](/python/basics).

Final Thoughts: Pair Those Sums

LeetCode 373: Find K Pairs with Smallest Sums in Python is a pairing challenge. The min-heap solution is the efficiency champ, while brute force builds intuition. Want more? Try LeetCode 215: Kth Largest Element or LeetCode 378: Kth Smallest Element in a Sorted Matrix. Ready to pair? Visit Solve LeetCode 373 on LeetCode and find those sums today!