Java Brute Force Solution with PriorityQueue, 150ms


  • 0
    R

    Just add all the possible pairs into the priorityQueue with size K.
    Time Complexity: O(mnlogK)
    Space: O(K)

    Code as follows:

    public class Solution {
        public class Pair{
            int i1;
            int i2;
            int sum;
            public Pair(int sum, int i1, int i2){
                this.sum = sum;
                this.i1 = i1;
                this.i2 = i2;
            }
        }
        public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
            List<int[]> result = new ArrayList<>();
            if(nums1 == null || nums2 == null) return result;
            int len1 = nums1.length, len2 = nums2.length;
    
            PriorityQueue<Pair> pq = new PriorityQueue<>((p1, p2) -> p2.sum - p1.sum);
            for(int i = 0; i < len1; i++){
                for(int j = 0; j < len2; j++){
                    int sum = nums1[i] + nums2[j];
                    if(pq.size() < k)
                        pq.offer(new Pair(sum, i, j));
                    else if (sum < pq.peek().sum) {
                        pq.poll();
                        pq.offer(new Pair(sum, i, j));
                    }
                }
            }
            
            while(!pq.isEmpty()){
                Pair p = pq.poll();
                result.add(0, new int[]{nums1[p.i1], nums2[p.i2]});
            }
            
            return result;
                
        }
    }
    

  • 0
    R

    @ran3 Any suggestion how can we optimize it?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.