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

• 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;
}
}
secondIndex[minIndex]++;//never use the same (minindex, secondIndex[minIndex]) pairs again :)
}
return result;
}
}
``````

How does it scale with respect to `k`:

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]

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