[Java 3ms (beats 100%)] Simple O(k) solution explained


  • 0
    E

    First of all let me start with the code itself:

    public class Solution {
        public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
            if (nums1.length == 0 || nums2.length == 0) return new ArrayList<int[]>();
            if (k > (nums1.length * nums2.length)) k = nums1.length * nums2.length;
            List<int[]> result = new ArrayList<>(k);
            int[] secondIndex = new int[nums1.length]; // init with all 0
            int index = 0;
            int minIndex = 0, min = 0, i = 0;
            while(k-- > 0)
            {
                if(secondIndex[index]>=nums2.length) index++;//if num2 has been fully travered for secondIndex[index] move on to next
                minIndex = index; // let' start start with index 
                /*
                    for each value to nums1 get index of nums2 with last best index+1
                    and consider it as minimum for the time being
                */
                min = nums1[index] + nums2[secondIndex[index]];
                i = index;
                /*
                    if there is a possibility to check the next index and secondIndex is anything but 0
                    it means there is a possibility of having even a better min value
                    thus we increament i for all the next values in secondIndex where secondIndex[i] is not 0
                    and its sum produces lesser than current min value
                    
                    if such a case occurs, replace minIndex with this index
                */
                while (i < secondIndex.length - 1 && secondIndex[i] != 0){
                    i++;
                    if (min > nums1[i] + nums2[secondIndex[i]]) {
                        min = nums1[i] + nums2[secondIndex[i]];
                        minIndex = i;
                    }
                }
                result.add(new int[]{nums1[minIndex], nums2[secondIndex[minIndex]]});
                secondIndex[minIndex]++;//never use the same (minindex, secondIndex[minIndex]) pairs again :)
            }
            return result;
        }
    }
    

    How does it scale with respect to k:

    0_1477207523995_image.png

    Since our outer loop is with respect to k and inner loop is with respect to nums1, the graph suggests that the inner loop is amortized O(1) step(I might be wrong).

    Thus, complexity of this algo is O(k).

    References:
    https://discuss.leetcode.com/topic/50773/java-3ms-beats-100-submission [Took inspiration from this solution]


Log in to reply
 

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