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)
                    sol.add((minn, maxx))

    findInArray(A, B, c)
    findInArray(B, A, c)
    return list(sol)


print(twoSumLessThen([1, 2, 3, 4, 5], [2, 3, 4], 5))
print(twoSumLessThen([1, 2, 3, 4, 5, 7, 8, 9, 100, 20, -40, 20, -10, -100], [2, 3, 4-1, -2, 0], 8))