Java 10ms solution no priority queue


  • 20

    Because both array are sorted, so we can keep track of the paired index. Therefore, we do not need to go through all combinations when k < nums1.length + num2.length. Time complexity is O(k*m) where m is the length of the shorter array.

    public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
            List<int[]> ret = new ArrayList<int[]>();
            if (nums1.length == 0 || nums2.length == 0 || k == 0) {
                return ret;
            }
            
            int[] index = new int[nums1.length];
            while (k-- > 0) {
                int min_val = Integer.MAX_VALUE;
                int in = -1;
                for (int i = 0; i < nums1.length; i++) {
                    if (index[i] >= nums2.length) {
                        continue;
                    }
                    if (nums1[i] + nums2[index[i]] < min_val) {
                        min_val = nums1[i] + nums2[index[i]];
                        in = i;
                    }
                }
                if (in == -1) {
                    break;
                }
                int[] temp = {nums1[in], nums2[index[in]]};
                ret.add(temp);
                index[in]++;
            }
            return ret;
        }
    

  • 0
    A

    Make sense! This solution is similar to "find nth ugly number"


  • 0
    B

    The k will between 1 and mn. So at worst case, time complexity is O(nm*m)


  • 1
    A

    To make the code faster, you can create the index with length of smaller size array.


  • 0
    E

    this code doesn't work for this test case
    [1,7,11]
    [2,4,6]
    6

    Your answer:
    [[1,2],[1,4],[1,6],[7,2],[7,4],[7,6]]

    Expected answer:
    [[1,2],[1,4],[1,6],[7,2],[7,4],[11,2]]


  • 1

    @etherbren 7+6 = 11+2 = 13 So... I don't think either is wrong. But if you change the '<' in 16th line to '<=', you will get what you want.

    if (nums1[i] + nums2[index[i]] <= min_val) {
        min_val = nums1[i] + nums2[index[i]];
        in = i;
    }
    

  • 0
    Z

    This is the best and correct solution IMO,


  • 1
    Z

    Here's my js solution base on yours. Thanks again for sharing.

    var kSmallestPairs = function(nums1, nums2, k) {
        let m = Array(nums1.length).fill(0),
            result = [], mark,
            temp;
        k = Math.min(nums1.length * nums2.length, k);
        
        while (k--) {
            temp = Number.MAX_SAFE_INTEGER;
            for (let i=0; i<m.length; i++) {
                if (nums1[i] + nums2[m[i]] < temp) {
                    mark = i;
                    temp = nums1[i] + nums2[m[i]];
                }
            }
            result.push([ nums1[mark], nums2[m[mark]] ]);
            m[mark]++;
        }
        return result;
    };
    

  • 0
    M

    @mylzsd Still doesn't work. Have a look at the following example:

    Input:

    [1,2,4]
    [-1,1,2]
    10

    Output:

    [[1,-1],[2,-1],[1,1],[4,-1],[2,1],[1,2],[2,2],[4,1],[4,2]] // the answer that the proposed solution gives
    [[1,-1],[2,-1],[1,1],[4,-1],[1,2],[2,1],[2,2],[4,1],[4,2]] // the expected answer

    In fact, I believe it's not a solution's issue; it's an issue of the problem specification: the order of pairs with equal sums is never defined.


  • 0
    H

    Thank you very much for sharing your solution. But could anyone explain what is the index array doing? I didn't get the reason we need it.


  • 0

    @huinixu It records the index of number in nums2 which currently paired with number in nums1.


  • 0
    H

    Thank you very much!


  • 0
    G

    if explanation is added that would be great.
    Code like this without comment is a bit difficult to understand, have to manually work out on an example to understand your code. something like the following are not easy to tell what they are really used for.

    int[] index = new int[nums1.length];
    int in = -1;


  • 1

    @mylzsd Thanks for sharing! Really intuitive solution!!
    I rewrite your code and change some variable names to make it more readable. I also add some comments in code and some explanations to express my understanding.

    Different from classical two pointer problems, we should use an array to record positions, since it does not necessarily always make sense that index2 will keep moving forward from previous position.

    If index1 move forward, the index2 should start from the first place in nums2
    for example nums1 = {1,3,4,5} and nums2 = {2,3,4,5}, when index1->1 && index2->2, sum = 1 + 2 = 3; then we keep moving, index1->1 && nums2->3 and sum = 1 + 3 = 4; keep going then index1->1 && index2->3 and sum = 1 + 4 = 5; if we keep moving index2 forward, then index1->1 && index2->5, it does not make sense since index1->3 && index2->2 should get smaller sum. You can see here, we move the index1 forward instead of index2 and reset index2 to 0 and start over again. Since we do not want to reset index2 every time when necessary, we can create an array since an array will initialize every position to value of 0.

    You can simple understand that you have a pair of index(index1, index2) in which case index2 = index2[index1], which means you can use only one variable index1 to record two variables(two positions in nums1 and nums2).

    public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
            List<int[]> ret = new ArrayList<int[]>();
            if(nums1.length == 0 || nums2.length == 0 || k == 0) return ret;
            
            //index2 is used for recording position in nums2 corresponding to given position in nums1
            int[] index2 = new int[nums1.length];
            while(k-- > 0){
                int min = Integer.MAX_VALUE;
                //every time we should start from the first place in nums2 to find proper position
                int index = -1;
                for(int index1 = 0; index1 < nums1.length; index1 ++){
                    if(index2[index1] >= nums2.length) continue;
                    
                    if(nums1[index1] + nums2[index2[index1]] < min){
                        min = nums1[index1] + nums2[index2[index1]];
                        //keep record the index in nums1
                        index = index1;
                    }
                }
                if(index == -1) break;
                
                int[] temp = {nums1[index], nums2[index2[index]]};
                ret.add(temp);
                index2[index] ++;
            }
            return ret;
        }
    

Log in to reply
 

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