algoadvance

Leetcode 373. Find K Pairs with Smallest Sums

Problem Statement

Given two integer arrays nums1 and nums2 sorted in ascending 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.

Example:

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

Constraints:

  1. 1 <= nums1.length, nums2.length <= 10^4
  2. -10^9 <= nums1[i], nums2[i] <= 10^9
  3. nums1 and nums2 are both sorted in ascending order.
  4. 1 <= k <= 10^4

Clarifying Questions

  1. Are there duplicates in the input arrays?
    • Yes, the arrays could contain duplicates.
  2. Are the input arrays always sorted?
    • Yes, both nums1 and nums2 arrays are already sorted in ascending order.
  3. If k is larger than the number of possible pairs, should we return all possible pairs?
    • Yes, if k is larger than the total number of pairs, return all possible pairs.

Strategy

  1. Min Heap Approach:
    • Use a min heap to always extract the smallest pair sum.
    • Initialize the heap with pairs from nums1 and the first element of nums2.
    • Iterate to pop the smallest pair from the heap, then push the next element from nums2 for the current element in nums1.
    • Continue until we have the desired k pairs or the heap is exhausted.
  2. Details:
    • Each entry in the heap will be of the form (sum, index1, index2), where sum = nums1[index1] + nums2[index2].
    • Pop the smallest entry, add the pair (nums1[index1], nums2[index2]) to the result, and push the next pair involving index1.

Time Complexity

Code

import java.util.*;

class Solution {
    public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<int[]> result = new ArrayList<>();
        if (nums1.length == 0 || nums2.length == 0 || k == 0) return result;

        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);

        for (int i = 0; i < nums1.length && i < k; i++) {
            minHeap.add(new int[] {nums1[i] + nums2[0], i, 0});
        }

        while (k > 0 && !minHeap.isEmpty()) {
            int[] current = minHeap.poll();
            int sum = current[0];
            int i = current[1];
            int j = current[2];
            result.add(new int[] {nums1[i], nums2[j]});
            k--;

            if (j + 1 < nums2.length) {
                minHeap.add(new int[] {nums1[i] + nums2[j + 1], i, j + 1});
            }
        }

        return result;
    }
}

This code uses a min heap to ensure the smallest pairs are processed first, efficiently keeping track of the next smallest pair to consider from nums1 and nums2.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI