Share My Solution which beat 96.42%


  • 48

    This problem is exactly the same as Leetcode378 Kth Smallest Element in a Sorted Matrix, the only difference is this problem give two array while 378 gives a matrix, but they are the same. You can check my previous post for 378 to see how it works.
    https://discuss.leetcode.com/topic/52948/share-my-thoughts-and-solution

    public class Solution {
        public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
            PriorityQueue<Tuple> pq = new PriorityQueue<Tuple>();
            int m = nums1.length, n = nums2.length;
            List<int[]> res = new ArrayList<int[]>();
            if(nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0 || k <= 0) return res;
            for(int j = 0; j <= n-1; j++) pq.offer(new Tuple(0, j, nums1[0]+nums2[j]));
            for(int i = 0; i < Math.min(k, m *n); i++) {
                Tuple t = pq.poll();
                res.add(new int[]{nums1[t.x], nums2[t.y]});
                if(t.x == m - 1) continue;
                pq.offer(new Tuple (t.x + 1, t.y, nums1[t.x + 1] + nums2[t.y]));
            }
            return res;
        }
    }
    
    class Tuple implements Comparable<Tuple> {
        int x, y, val;
        public Tuple (int x, int y, int val) {
            this.x = x;
            this.y = y;
            this.val = val;
        }
        
        @Override
        public int compareTo (Tuple that) {
            return this.val - that.val;
        }
    }
    

  • 2
    M

    Clear solution!
    Just a small detail: As there are int m = nums1.length, n = nums2.length, the checking of num1 == null and num2 == null is useless.


  • 0
    A

    In the line for(int i = 0; i < Math.min(k, m *n); i++)

    Could you explain this condition Math.min(k, m *n)? I'm not exactly sure why we need to compare the minimum of k and m*n


  • 0
    H

    @aoben10 m * n is a maximum number of tuples that can be generated from two arrays. If k is greater than this number, the loop will go beyond arrays. Math.min(k, m * n) picks up the loop limitation accordingly.


  • 0
    F

    Nice and clear solution. Thanks for sharing!
    One small question: how to explain its time complexity in an interview? Suppose the length of nums1 and nums2 are m and n, should the time complexity be O((n+k)*logn) when k < m*n, otherwise O((n+m*n)*logn)?


  • 0
    Y

    great solution! this is k-way merge sort.


Log in to reply
 

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