Find K Smallest Sum Pairs

JavaView on GFG

Intuition

Find k pairs (one from each sorted array) with smallest sums. Min-heap.

Algorithm

1Push (arr1[0]+arr2[j], 0, j) for j=0..k-1 into min-heap. Pop k times, each time push (arr1[i+1]+arr2[j], i+1, j).

Common Pitfalls

•Same as LC 373. Initial seeds from first element of arr1 with all of arr2. Pop and expand.

Find K Smallest Sum Pairs.java

Java

// Approach: Min-heap of size k. Start with (arr1[0]+arr2[0]), expand by incrementing indices.
// Time: O(k log k) Space: O(k)
import java.util.*;

class Solution {
    public ArrayList<ArrayList<Integer>> kSmallestPair(int[] arr1, int[] arr2, int k) {
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
        int n = arr1.length;
        int m = arr2.length;
        if (n == 0 || m == 0 || k == 0)
            return ans;

        PriorityQueue<Pair> pq = new PriorityQueue<>((a, b) -> a.sum - b.sum);

        for (int i = 0; i < Math.min(k, n); i++)
            pq.add(new Pair(arr1[i] + arr2[0], i, 0));

        while (k-- > 0 && !pq.isEmpty()) {
            int i = pq.peek().i;
            int j = pq.peek().j;
            pq.poll();

            ArrayList<Integer> temp = new ArrayList<>();
            temp.add(arr1[i]);
            temp.add(arr2[j]);
            ans.add(temp);

            if (j + 1 < m)
                pq.add(new Pair(arr1[i] + arr2[j + 1], i, j + 1));
        }

        return ans;
    }

    class Pair {
        int sum, i, j;

        Pair(int sum, int i, int j) {
            this.sum = sum;
            this.i = i;
            this.j = j;
        }
    }
}

Was this solution helpful?