1
\$\begingroup\$

I'm trying to map this problem into a 4-sum problem, and I find the time complexity is always \$O(n^3)\$. Is there a way to optimize time complexity, with constant additional space complexity \$O(1)\$?

Any other advice about improvement for time complexity, code bugs or code style advice is appreciated.

Problem

Given an array A of unique integers, find the index of values that satisfy A + B =C + D, where A,B,C & D are integers values in the array. Find all combinations of quadruples.

def four_sum (numbers, target, start, end, exclude_index_set):
    i = start
    j = end
    result = []
    while i < j:
        if i in exclude_index_set:
            i += 1
        elif j in exclude_index_set:
            j -= 1
        elif numbers[i] + numbers[j] == target:
            result.append((numbers[i], numbers[j]))
            i += 1
            j -= 1
        elif numbers[i] + numbers[j] > target:
            j -= 1
        else:
            i += 1
    return result

if __name__ == "__main__":
    numbers = [1,2,3,4]
    result = []
    for i,v in enumerate(numbers):
        for j in range(i+1, len(numbers)):
            r = four_sum(numbers, v+numbers[j], i+1, len(numbers)-1, set([i,j]))
            if len(r) > 0:
                r.append(([numbers[i],numbers[j]]))
                result.append(r)
    print result
\$\endgroup\$
  • 1
    \$\begingroup\$ If your goal is to output all quadruples, then you cannot get solution faster than O(n^4), because you have to generate the answer somehow. \$\endgroup\$ – yeputons Feb 7 '17 at 7:37
  • 3
    \$\begingroup\$ @yeputons Since the numbers are unique, there can only be at max \$O(n^3)\$ solutions. This is because, for any given A, B, C, there can be at most one D that solves the equation. If duplicates were allowed, then up to n-3 values of D could solve the equation. \$\endgroup\$ – JS1 Feb 7 '17 at 9:43
  • \$\begingroup\$ @JS1 you're right, I missed the fact that numbers are unique. However, one still has to find all of them if they are to be printed. \$\endgroup\$ – yeputons Feb 7 '17 at 11:17
  • \$\begingroup\$ The problem statement seems to allow all doubled pairs of indices: n[a]+n[b] == n[a]+n[b] and n[a]+n[b] == n[b]+n[a] for any a,b in the index range, so there's always at least \$2N(N-1)\$ quadruples in the solution, where \$N\$ – the input array's length. \$\endgroup\$ – CiaPan Feb 7 '17 at 13:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.