373. Find K Pairs with Smallest Sums (https://leetcode.com/problems/find-k-pairs-with-smallest-sums/description/): You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k. Define a pair (u,v) which consists of one element from the first array and one element from the second array. Find the k pairs (u1,v1),(u2,…

373. Find K Pairs with Smallest Sums (#1 Heap).java

//Heap solution: Same sum matrix with 378
//Time: O(klogk)
//Space: O(k)
class Solution {
    public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<int[]> ans = new ArrayList<>();
        if(nums1.length == 0 || nums2.length == 0) return ans;
        //Sum matrix: nums1 is the row title, nums2 is the column title
        //Build a minHeap of the elements from the first row
        PriorityQueue<Tuple> minHeap = new PriorityQueue<>();
        for(int i = 0; i < nums1.length && i < k; i++)
            minHeap.add(new Tuple(i, 0, nums1[i] + nums2[0]));
        //Everytime when you poll out the root, replace the element with the next element of the same column
        while(k-- > 0) {
            Tuple pair = minHeap.poll();
            if(pair == null) break;
            ans.add(new int[]{nums1[pair.x], nums2[pair.y]});
            if(pair.y == nums2.length - 1) continue;
            minHeap.add(new Tuple(pair.x, pair.y + 1, nums1[pair.x] + nums2[pair.y + 1]));
        }
        return ans;
    }
}

class Tuple implements Comparable<Tuple> {
    int x;
    int y;
    int val;
    public Tuple(int x, int y, int val) {
        this.x = x;
        this.y = y;
        this.val = val;
    }
    
    public int compareTo(Tuple that) {
        return this.val - that.val;
    }
}