Count all unique quadruples that sum to a given value - is N^3 complexity algorithm known?

Question

I am supposed to solve this problem in as low time complexity as possible, but let me be more specific.

You are given a sorted array of integers that contains duplicates.

Unique quadruple is a set of four indexes. Elements from the array under those indexes have to sum to a given value X. For example:

1. Given an array [10, 20, 30, 40] and X = 100, there is only one quadruple: (0, 1, 2, 3).

2. Given an array [0, 0, 0, 0, 0] and X = 0, there are 5 quadruples: (0, 1, 2, 3), (0, 1, 2, 4), (0, 1, 3, 4), (0, 2, 3, 4), (1, 2, 3, 4).

On the Internet there are plenty of N^3 solutions, but those are for unique quadruples in terms on values, not indexes. In those solutions, example number 1 would still give only one quadruple: (10, 20, 30, 40), but example number 2 gives only one quadruple (0, 0, 0, 0), not five of them.

I couldn't find a O(N^3) solution that would solve my problem instead of the other one. I can easily write a program that solves it in O(N^3logN) time. I also heard that the lower complexity bound for this problem is allegedly not known. Is there a O(N^3) solution known though?

Solutions known to me:

1. Obvious naive approach O(N^4):

   int solution(int arr[], int arrSize, int X){
       int counter = 0;
       for(int i=0; i<arrSize-3; ++i)
           for(int j=i+1; j<arrSize-2; ++j)
               for(int k=j+1; k<arrSize-1; ++k)
                   for(int l=k+1; l<arrSize; ++l)
                       if(arr[i] + arr[j] + arr[k] + arr[l] == X)
                           ++counter;
       return counter;
   }
   

2. Approach using triplets and binary search O(N^3logN):

   int solution(int arr[], int arrSize, int X){
       int counter = 0;
       for(int i=0; i<arrSize-3; ++i)
           for(int j=i+1; j<arrSize-2; ++j)
               for(int k=j+1; k<arrSize-1; ++k){
                   int subX = X - arr[i] - arr[j] - arr[k];
                   int first = binFirst(subX, arr, k+1, arrSize);
                   // Binary search that returns the position of the first
                   // occurrence of subX in arr in range [k+1, arrSize)
                   // or -1 if not found
                   int last = binLast(subX, arr, k+1, arrSize);
                   // Binary search that returns the position of the last
                   // occurrence of subX in arr in range [k+1, arrSize)
                   // or -1 if not found
                   if(first != -1)
                       counter += last - first + 1;
       return counter;
   

Naturally, the above algorithm could be improved by counting all duplicates of arr[i], arr[j], arr[k], but as far as I can tell, it does not lower the actual O(N^3logN) complexity.

Answer 1

O(n²) in Python, inspired by גלעד ברקן's answer:

from itertools import combinations
from collections import Counter

def solution(arr, X):
    cd = Counter(map(sum, combinations(arr, 2)))
    count = 0
    for i, b in enumerate(arr):
        for d in arr[i+1:]:
            cd[b+d] -= 1
        for a in arr[:i]:
            count += cd[X - (a+b)]
    return count

Call the quadruples (a,b,c,d). We focus on the second element, b. For each possible b, we add each possible a (elements left of b), and look up how many pairs (c,d) (elements right of b) complete the sum a+b+c+d = X, i.e., sum to X - (a+b). For that lookup, we have a hash map cd that maps sums of pairs to counts of pairs. Initially, that's all pairs of the whole arr, but for each b we consider, remove its contributions to the map.

C++ version, where a/b/c/d are indexes instead of elements:

int solution(int arr[], int n, int X){
  std::unordered_map<int, int> cd;
  for (int c=0; c<n; c++)
    for (int d=c+1; d<n; d++)
      cd[arr[c]+arr[d]]++;
  int count = 0;
  for (int b=0; b<n; b++) {
    for (int d=b+1; d<n; d++)
      cd[arr[b]+arr[d]]--;
    for (int a=0; a<b; a++)
      count += cd[X - (arr[a]+arr[b])];
  }
  return count;
}

Python code with testing (Try it online!):

from itertools import combinations
from collections import Counter

def solution(arr, X):
    cd = Counter(map(sum, combinations(arr, 2)))
    count = 0
    for i, b in enumerate(arr):
        for d in arr[i+1:]:
            cd[b+d] -= 1
        for a in arr[:i]:
            count += cd[X - (a+b)]
    return count

import random
from operator import countOf

def naive(arr, X):
    sums = map(sum, combinations(arr, 4))
    return countOf(sums, X)

arr = random.choices(range(100), k=100)
print(naive(arr, 200))
print(solution(arr, 200))

C++ code with testing.

Answer 2

Detailed explanation of how to come to the best solution step by step

Let's invent the solution.

Now, if we create pairs that contain sums of pairs, for example,

arr = [10, 20, 30, 40]
pairs = [10+20, 10+30, 10+40, 20+30, 20+40, 30+40]

There is a pattern. We have three pairs for 10+x, two pairs for 20+x, one pair for 30+x, and zero pairs for 40+x.

 [10+20, 10+30, 10+40, 20+30, 20+40, 30+40]
# -------------------  ------------  -----

 [30, 40, 50, 50, 60, 70]
# ----------  ------  --

So, the total pairs are

3 + 2 + 1
= sum of first (n-1) natural numbers
= (n - 1) * (n - 1 + 1) / 2
= (n - 1) * n / 2
= (n^2 - n) / 2

It looks like the whole pairs array will be sorted, but it is not true. Those sub-arrays in pairs should be sorted because the initial arr is sorted. For example,

arr = [10, 20, 30, 90]
pairs = [10+20, 10+30, 10+90, 20+30, 20+90, 30+90]

# Those sub-arrays are sorted
 [30, 40, 100, 50, 110, 120]
# -----------  -------  ---

Now, let’s write the pairs with origin arr indices

pairs = [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]

(0, 1) and (0, 2) are not valid quadruples, because we are having 0 in both pairs. So, how can we logically find valid pairs?

We only have one valid pair for (0, 1) which is (2, 3) which does not have 0 or 1

 [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
#  x  x    x       x       x       x       ----

One fact is, we can always write quadruple in such a way that one pair is next to the other pair. For example,

x = 100
arr = [10, 20, 30, 40]
pairs = [30, 40, 50, 50, 60, 70]

 [10, 20, 30, 40]
# --  ------  --
quadruple = (10 + 40) + (20 + 30)

# Which can we rewrite as
 [10, 20, 30, 40]
# ------  ------
quadruple = (10 + 20) + (30 + 40) = 30 + 70

# Which is as follows
pairs = [30, 40, 50, 50, 60, 70]
#        --                  --

So, we can do as follows to solve the problem

for pair0 in pairs:
    valid_pairs_for_pair0 = # Somehow get the valid pairs
    for pair1 in valid_pairs_for_pair0:
        if pair0 + pair1 == x:
            ans += 1

But the above solution is O(n^4), because pairs is of length (n^2 - n) / 2.

We can do better as we know those sub-arrays in the pairs are sorted.

arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] # n = 10
pairs = [
  (0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(0,7),(0,8),(0,9),# (0,x) -> 9 pairs -> 10 - 0 - 1
  (1,2),(1,3),(1,4),(1,5),(1,6),(1,7),(1,8),(1,9),# (1,x) -> 8 pairs -> 10 - 1 - 1
  (2,3),(2,4),(2,5),(2,6),(2,7),(2,8),(2,9),# (2,x) -> 7 pairs -> 10 - 2 - 1
  (3,4),(3,5),(3,6),(3,7),(3,8),(3,9),# (3,x) -> 6 pairs -> 10 - 3 - 1
  (4,5),(4,6),(4,7),(4,8),(4,9),# (4,x) -> 5 pairs -> 10 - 4 - 1
  (5,6),(5,7),(5,8),(5,9),# (5,x) -> 4 pairs -> 10 - 5 - 1
  (6,7),(6,8),(6,9),# (6,x) -> 3 pairs -> 10 - 6 - 1
  (7,8),(7,9),# (7,x) -> 2 pairs -> 10 - 7 - 1
  (8,9),# (8,x) -> 1 pair -> 10 - 8 - 1
]

# We need to find the first valid pair and all of the pairs after that will be valid.

first valid pair index for (0, 1) => first (2,x) pair => (2,3) => pairs[9 + 8]
first valid pair index for (0, 2) => first (3,x) pair => (3,4) => pairs[9 + 8 + 7]
first valid pair index for (0, 3) => first (4,x) pair => (4,5) => pairs[9 + 8 + 7 + 6]

# There is a pattern
pairs[9 + 8] => pairs[sum(9 to 1) - sum(7 to 1)]
pairs[9 + 8 + 7] => pairs[sum(9 to 1) - sum(6 to 1)]
pairs[9 + 8 + 7 + 6] => pairs[sum(9 to 1) - sum(5 to 1)]

# That’s how we get started and for binary search
start = firstNSum(n - 1) - firstNSum(n - i1 - 2)
end = start + n - (i1 + 1) - 1 # n - (i1 + 1) - 1 is the number of pairs for (i1,x) pairs

Now, we can solve the problem as follows.

# For pair0 in pairs:
    # Binary search for all valid sub-arrays of pairs for pair0

Solution 1: Binary search

Time complexity: O(n^3.log(n)) log(n) + log(n-1) ... log(1) = log(n!) = n.log(n)

Space complexity: O(n^2)

def firstNSum(n):
    return n * (n + 1) // 2

def binary_search(pairs, x, start, end):
    while start < end:
        mid = (start + end) // 2
        if pairs[mid][1] < x:
            start = mid + 1
        else:
            end = mid
    return start


def count_four_pairs_with_sum(arr, x):
    n = len(arr)

    ans = 0

    pairs = []

    for i0 in range(n - 1):
        for i1 in range(i0 + 1, n):
            curr_sum = arr[i0] + arr[i1]
            pairs.append([(i0, i1), curr_sum])

    for [(i0, i1), curr_sum] in pairs:

        start = firstNSum(n - 1) - firstNSum(n - i1 - 2)
        end = start + n - (i1 + 1) - 1

        while start < len(pairs):
            x_start = binary_search(pairs, x - curr_sum, start, end)
            x_end = binary_search(pairs, x - curr_sum + 1, start, end)

            ans += x_end - x_start

            i1 += 1
            start += n - i1 - 1
            end = start + n - (i1 + 1) - 1

    return ans

arr = [10, 20, 30, 40]
x = 100
print(count_four_pairs_with_sum(arr, x))

We can do better. If we store the number of pairs with sum alongside with that also storing how many pairs are from each (i, x) pair group from pairs

# Loop for i0
    # Loop for i1
        # ans += valid pairs for i0 and i1, which is sum of i1 to n excluding i0 to i1

Solution 2: Using hashmap

Time complexity: O(n^3)

Space complexity: O(n^3)

from collections import defaultdict

def count_four_pairs_with_sum(arr, x):
    n = len(arr)

    ans = 0

    sum_freq = defaultdict(lambda: defaultdict(int))

    for i0 in range(n - 1):
        for i1 in range(i0 + 1, n):
            curr_sum = arr[i0] + arr[i1]
            sum_freq[curr_sum][i0] += 1

    for i0 in range(n - 1):
        for i1 in range(i0 + 1, n):
            curr_sum = arr[i0] + arr[i1]
            needed_sum = x - curr_sum
            valid_needed_sum_count = sum([sum_freq[needed_sum][i] for i in range(i1+1, n)])
            ans += valid_needed_sum_count

    return ans


arr = [0, 0, 0, 0, 0]
x = 0
print(count_four_pairs_with_sum(arr, x))

We can do better (as this answer showed) if we have frequencies of all possible pairs, and we look for all valid pair1 for each pair0.

Let a + b + c + d = x

a can be any number on the left of b

c and d can be any pair right of b

Because we know, we can rewrite any quadruple in such a way that a < b < c < d, for example,

 [0, 1, 2, 3, 4, 5, ...., n-1, n]
#       a     b            c   d

So, for any b we only need to count the valid (c,d) to the right of it, which means we don't need to consider any pair containing any number that is left to b for example (c,d)=(2,5) is invalid if b=4 because 2 is left of 4

Now, we can solve that as follows.

# For every b
  # Remove all pairs for b
  # For every valid a, a < b
    # ans += number of valid pairs in remaining pairs

The first loop for b will keep removing pairs for current b that means when b=4 we already removed all pairs from previous values of b=1,2,3

Final solution: Using hashmap

Time complexity: O(n^2)

Space complexity: O(n^2)

from collections import defaultdict

def count_four_pairs_with_sum(arr, x):
    n = len(arr)

    sum_freq = defaultdict(int)

    for i0 in range(n - 1):
        for i1 in range(i0 + 1, n):
            curr_sum = arr[i0] + arr[i1]
            sum_freq[curr_sum] += 1

    ans = 0
    for i, b in enumerate(arr):

        for j in arr[i+1:]:
            sum_freq[b+j] -= 1

        for a in arr[:i]:
            c_plus_d = x - (a+b)
            ans += sum_freq[c_plus_d]

    return ans

arr = [0, 0, 0, 0, 0]
x = 0
print(count_four_pairs_with_sum(arr, x))

Answer 3

We can do it in O(n^2) time and space by dynamically updating.

(See Kelly Bundy's answer for simpler and more efficient space usage.)

Start by creating the hash-map of sum to set of index-pairs that compose it, traversing from the left, and store for each index, the pairs it belongs to (O(n) of them), until the right two elements are left and not hashed.

Now traverse towards the left: starting with the third rightmost element, remove all the pairs the current element belongs to (O(n) of them). Then for each sum the element can create by pairing with an element on its right, add the count of pairs in the corresponding hashed sum that would complete the overall sum. Because we removed all instances where the current element was used on the left, we are guaranteed to have partitioned quadruples, where none on the right are represented in the hashed counts from the left.