# Potential O(k) solution....but have a bug for several test cases... Anyone Help please. Explanation inside...

• ``````    //not sure why im receving error for this solution.
//the idea is to store the current pointer of the other array for each index of the current array.
//ie for arrays nums1 = [1,2,5] , nums2 = [1,1,2],
//after we stored result = (1,1), (1,1), (2,1), (2,1)
// with indexes ---------= (0,0), (0,1), (1,0), (1,1)
//the stored pointer array s1 for ptr2 would be [1,1,0]
//the stored pointer array s2 for ptr1 would be [1,1,0]
//we determine which two numbers to compare by checking (i + 1, stored pointer2 for index i+1)
//(stored pointer1 for index j + 1, j + 1)
//thus, the next iteration for storing would check indexes (2,0) and (0,2), and choose the smallest one to proceed forward.
//in this iteration, we see that for indexes(2,0) we get 5 + 1, for indexes (0,2) we get 2 + 2.
//thus we choose (0,2) with values 2 and 2.
//since we incremented the second pointer, we store the value in s2 => ["2",1,0].
//I use a visited set to prevent revisiting equal indexes, ie (1,1), (2,2), etc.
//the runtime of this would be k........+ all the duplicates you visit. Worst case is 2K (if you revisit all the duplicates once...)
//i get array out of bounds exception and cannot figure out why, if someone could give insight that would be great...works for simple test cases : |
public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
List<int[]> res = new ArrayList<>();
Set<String> visited = new HashSet<>();
if (nums1.length == 0 || nums2.length == 0 || k == 0) return res;
int i = 0;
int j = 0;
int[] s1 = new int[nums1.length]; // store j ptrs for each i index
int[] s2 = new int[nums2.length]; //store  i ptrs for each j index
while (res.size() < k) {
if (!visited.contains(i + " " + j))res.add(new int[]{nums1[i], nums2[j]});
visited.add(i + " " + j);
if (i == nums1.length - 1 && j == nums2.length -1) break;
else {
boolean choose = false; //if choose is true, we increment j by one, and set i to s2[j]. then increment s2[j] afterwards.
// otherwise you do the opposite...
if (i == nums1.length - 1) {
choose = true;
}
else if (j == nums2.length - 1) {
} else {
int sum1 = nums1[i + 1] + nums2[s1[i + 1]];
int sum2 = nums2[j + 1] + nums1[s2[j + 1]];
if (sum1 > sum2) {
choose = true;
}
}

if (choose) {
j++;
i = s2[j]++;
} else {
i++;
j = s1[i]++;
}

}
}
return res;
}
}``````

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