Find the index of the pair-wise sum


  • 0
    P

    Given two arrays, (say [1,3,5] and [2,4]) and a number target (say 7), assume we sort by the sum of any pair of elements from each array, return the smallest index.

    In this example, the result is 3.
    Pair, Sum, Index
    (1,2), 3, 0
    (1,4), 5, 1
    (3,2), 5, 2
    (3,4), 7, 3 <- result
    (5,2), 7, 4
    (5,4), 9, 5


  • 0

    time complexity: O(n*m)
    space complexity: O(1)

    def solution(nums_a, nums_b, t):
        # return -1 if invalid / not found
    
        if not nums_a or not nums_b or not t:
            return -1
    
        i = 0
        for a in nums_a:
            for b in nums_b:
                if a + b == t:
                    return i
                i += 1
    
        return -1
    

  • 0
    P

    @mattlee42011-hotmail.com

    Thanks, actually we could do better than O(nm), with binary search, we could do O(nlogm)


  • 0
    P
    // find lower bound: the largest index strictly smaller than a given number
    	int lowerBound(int[] nums, int target) {
    		int start = 0, end = nums.length - 1;
    		while(start <= end) {
    			int mid = start + (end - start)/2;
    			if(nums[mid] >= target) {
    				end = mid - 1;
    			} else {
    				start = mid + 1;
    			}
    		}
    		return end;
    	}
    
     int findIndex(int[] nums1, int[] nums2, int target) {
    		Arrays.sort(nums1);
    		Arrays.sort(nums2);
    		int res = 0;
    		boolean hasRes = false;
    		for(int i = 0; i< nums1.length; i++) {
    			int lb =  lowerBound(nums2, target - nums1[i]) + 1;
    			if(lb < nums2.length && nums2[lb] == target - nums1[i])
    				hasRes = true;
    			res += lb;
    		}
    		if(hasRes)
    			return res;
    		return -1;
    	}
    

  • 0
    M
    This post is deleted!

  • 0
    M

    @paul_416, Unfortunately @mattlee42011-hotmail-com's solution wont work. Imagine the given input is [2,4] and [3,8] and target is 10. His solution would return 1 since the first pair sum would be 5 and the next would be 10 but it would be incorrect since the correct order is [5,7,10,12] and the answer is index 2. Your solution, on the other hand, is very clever. Thanks for sharing it. Below is a python version inspired by it.

    The reason I keep nums1 to be the smaller array is that I want my complexity to be O(nlogm) where m is the length of the larger array. Hence, I am speeding it up by taking the logarithm of the larger array.

    import bisect
    def pairwisesum(nums1, nums2, target):
        if not nums1 or not nums2: return -1
        nums1.sort()
        nums2.sort()
        n, m = len(nums1), len(nums2)
        if n > m:
            nums1, nums2 = nums2, nums1
            n, m = m, n
        count = 0
        for n in nums1:
            i = bisect.insert_left(nums2, target - n)
            if i >= 0 and i < m and nums2[i] == target - n:
                count += i
                return i
            count += i
        return -1
    

Log in to reply
 

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