# Find the index of the pair-wise sum

• 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

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

``````def solution(nums_a, nums_b, t):

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
``````

• @mattlee42011-hotmail.com

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

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

• This post is deleted!

• @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
``````

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