Two Sum Less Than

Given two int arrays A and B, and an int c, return the total number of pairs (a, b) where a is from A and b is from B, and a + b <= c.

The Idea: We can brute force all computational pairs between a and b that are less than or equal to c in N^2 time. We can maintain a set of unique computational pairs to avoid duplicates. Another approach would be to sort both A and B, and for then find the largest point where a <= c - b in the target array. Do with for both arrays.

Complexity: O(|A|log|A| + |B|log|B| + |A|log|B| + |B|log|A| + |A| + |B|) and O(|A| + |B|) space. For the time complexity, sorting both arrays, then iterating through A calling binary search, then the reverse, and in the end, converting the solution set into a list.

def b_search(ar, left, right, target):
if left <= right:
mid = int(left + (right - left) / 2)
if mid == len(ar) - 1:
if ar[mid] <= target:
return mid
else:
return -1
if ar[mid] <= target and ar[mid + 1] > target:
return mid
elif ar[mid] > target and ar[mid + 1] > target:
return b_search(ar, left, mid - 1, target)
else:
return b_search(ar, mid + 1, right, target)
else:
return -1

def twoSumLessThen(A, B, c):
B = sorted(B)
A = sorted(A)
sol = set()

def findInArray(A, B, c):
for a in A:
# a + b <= c
# a <= c - b
target = c - a
target_i = b_search(B, 0, len(B) - 1, target)
if target != -1:
for i in range(0, target_i + 1):
minn, maxx = min(B[i], a), max(B[i], a)