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


  • 0
    I
        //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;
        }
    }

Log in to reply
 

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