We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find K Pairs with Smallest Sums

Number: 373

Difficulty: Medium

Paid? No

Companies: LinkedIn, Amazon, Meta, Google, Microsoft, Walmart Labs, Flipkart, Bloomberg, Uber

Problem Description

Given two integer arrays nums1 and nums2 sorted in non-decreasing order and an integer k, return the k pairs (u, v) with the smallest sums where u is from nums1 and v is from nums2.

Key Insights

  • Both arrays are sorted, making it possible to efficiently traverse and pick the smallest candidate pairs.
  • A min-heap (priority queue) can be used to always access the next smallest sum pair.
  • Instead of generating all possible pairs (which could be very large), we only generate candidates and push new pairs from nums2 as needed.

Space and Time Complexity

Time Complexity: O(k log(min(k, n1))) where n1 is the size of nums1, since we push at most min(k, n1) elements into the heap. Space Complexity: O(min(k, n1)) for storing the heap elements.

Solution

We use a min-heap (priority queue) to efficiently track and extract the pair with the smallest sum. Initially, we push pairs composed of each element in nums1 (up to k elements) paired with the first element of nums2. Each element in the heap is a tuple containing (sum, index in nums1, index in nums2). Every time we extract the smallest pair, we add the next pair from nums2 (if available) for that index in nums1. This approach ensures we always have the next smallest pair available and avoids creating all possible pairs upfront.

Code Solutions

import heapq

def kSmallestPairs(nums1, nums2, k):
    # Edge case: if either array is empty, return an empty list
    if not nums1 or not nums2 or k <= 0:
        return []
    
    result = []
    minHeap = []
    
    # Initialize the heap with the first element from nums2 for each element in nums1 (up to k)
    for i in range(min(k, len(nums1))):
        # Each entry: (sum, index in nums1, index in nums2)
        heapq.heappush(minHeap, (nums1[i] + nums2[0], i, 0))
    
    # Extract the smallest pairs until we found k pairs or the heap is empty
    while k > 0 and minHeap:
        currentSum, i, j = heapq.heappop(minHeap)
        result.append([nums1[i], nums2[j]])
        k -= 1
        # If there's any next element in nums2, push the new pair into the heap
        if j + 1 < len(nums2):
            heapq.heappush(minHeap, (nums1[i] + nums2[j + 1], i, j + 1))
    
    return result

# Example usage:
print(kSmallestPairs([1,7,11], [2,4,6], 3))
← Back to All Questions