BinarySearch 0699 Sum of Four Numbers Less Than Target

Problem statement

https://binarysearch.com/problems/Sum-of-Four-Numbers-Less-Than-Target/

Solution

First, we can create all sums from A and B and sort them. Then we can use binary search to find for each sum in C and D.

Complexity

It is O(n^2 log n) fo time and O(n^2) for space.

Code

class Solution:
    def solve(self, A, B, C, D, target):
        ab = sorted(a + b for a in A for b in B)
        return sum(bisect.bisect(ab, target - c - d) for c in C for d in D)