Practice/LinkedIn/Leetcode 373. Find K Pairs with Smallest Sums

Leetcode 373. Find K Pairs with Smallest Sums

CodingOptional

Problem

You are given two integer arrays nums1 and nums2, both sorted in non-decreasing order, and an integer k.

Your task is to find the k pairs (u, v) where u is an element from nums1 and v is an element from nums2, such that these pairs have the smallest sums among all possible pairs.

Return the pairs in any order. Each pair should be represented as a list [u, v] where u comes from nums1 and v comes from nums2.

Requirements

1. Return exactly k pairs, or all possible pairs if fewer than k pairs exist
2. Each pair must contain one element from nums1 and one element from nums2
3. The k pairs returned should have the k smallest sums among all possible pairs
4. Both input arrays are sorted in non-decreasing order
5. The output pairs can be in any order

Constraints

• 1 ≤ nums1.length, nums2.length ≤ 105
• -109 ≤ nums1[i], nums2[i] ≤ 109
• nums1 and nums2 are sorted in non-decreasing order
• 1 ≤ k ≤ 104
• Aim for O(k log k) time complexity to handle large inputs efficiently

Examples

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 with smallest sums are: (1, 2) with sum 3 (1, 4) with sum 5 (1, 6) with sum 7 Note that (7, 2) with sum 9 would come next.

Example 2:

Input: nums1 = [1, 1, 2], nums2 = [1, 2, 3], k = 2 Output: [[1, 1], [1, 1]] Explanation: The first 2 pairs with smallest sums are: (1, 1) with sum 2 (1, 1) with sum 2 (using the second 1 from nums1)

Example 3:

Input: nums1 = [1, 2], nums2 = [3], k = 3 Output: [[1, 3], [2, 3]] Explanation: Only 2 pairs are possible, so return both even though k = 3.