[LeetCode 373] Find K pairs with

class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<List<Integer>> result = new ArrayList<> ();
        if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
            return result;
        }
        
        //1. find all combination
        int[][] combinations = new int[nums1.length * nums2.length][2];
        int combinationIndex = 0;
        
        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                combinations[combinationIndex][0] = nums1 [i];
                combinations[combinationIndex][1] = nums2 [j];
                
                //System.out.println (Arrays.toString (combinations[combinationIndex]));
                combinationIndex ++;
            }
        }
        
        //2. scan all combinations and put into a priorityQueue (maxHeap)
        PriorityQueue <int[]> tracker = new PriorityQueue <int[]> (new Comparator <int[]> () {
            public int compare (int[] num1, int[] num2) {
                return (num2[0] + num2[1]) - (num1[0] + num1[1]);
            }
        });
        
        for (int[] combination : combinations) {
            if (tracker.size () < k) {
                tracker.offer (combination);
                continue;
            }
            
            int currentSum = combination [0] + combination [1];
            int[] currentTop = tracker.peek ();
            
            if (currentSum < currentTop [0] + currentTop [1]) {
                tracker.poll ();
                tracker.offer (combination);
            }    
        }
            
        while (!tracker.isEmpty ()) {
            List<Integer> temp = new ArrayList<> ();
            int[] combination = tracker.poll ();
            temp.add (combination[0]);
            temp.add (combination[1]);
            result.add (temp);
        }
        
        return result;
    }
}