CODEWITHSUNDEEP
arraysalgorithm
Sushil Verma
Sushil Verma

Reputation: 697

Quadruples in Array satisfying constraint

In an array A[1...n] of positive integers, you are to count all quadruples in array satisfying:

A[i] + A[j] + A[k] = A[l] where 1 <= i < j < k < l <=n

I tried many things but could not come to a solution better than O(n^3logn)

Can we solve it in O(n^3) or O(n^2) satisfying the ordering constraint of indices?

Upvotes: 3

Views: 247

Answers (2)

גלעד ברקן
גלעד ברקן

Reputation: 23945

Why not O(n^2)? If we have 

A[i] + A[j] + A[k] = A[l]
  where 1 ≤ i < j < k < l ≤ n

and we hashed all

A[i] + A[j] pairs
   where 1 ≤ i < j < n - 1

then we can iterate:

l = n
k = n - 1

check if A[l] - A[k] is in the hash

now update on each element as we descend:

j = n - 2

remove each instance of A[j] + A[i] in the hash
  where 1 ≤ i < j

for each instance of A[l] - A[j]
  where j < l < n
  check if a value exists in the hash

j = j - 1
...

Attempt in JavaScript:

function f(A){
  if (A.length < 4)
    return 0;
  let n = A.length;
  let hash = {};
  let i = 0;
  let j;
  let k;
  let l;
  let sum;
  let diff;
  let count = 0;
  
  // Hash sums up to A[n - 3]
  // in O(n^2) time
  for (; i<n-3; i++){
    for (j=i+1; j<n-2; j++){
      sum = A[i] + A[j];
      hash[sum] = hash[sum] ? hash[sum] + 1 : 1;
    }
  }

  diff = A[n-1] - A[n-2];
  if (hash[diff])
    count = count + hash[diff];
  
  // Iterate on j descending,
  // updating the hash each time,
  // O(n) times
  for (; j>1; j--){
    // Remove instances of j in
    // the hash in O(n) time
    for (i=j-1; i>=0; i--){
      sum = A[i] + A[j];
      hash[sum] = hash[sum] - 1;
    }
    
    // Check for valid quadruples
    // in O(n) time
    // where the old j is now k
    k = j;
    for (l=k+1; l<n; l++){
      diff = A[l] - A[k];
      if (hash[diff])
        count = count + hash[diff];
    }
  }
  
  return count;
}

/*
1 1 1 1 3 3

x x x   x
x x x     x
x x   x x
x x   x   x
x   x x x
x   x x   x
  x x x x
  x x x   x
  
Total 8
*/
var A = [1,1,1,1,3,3];
console.log(JSON.stringify(A))
console.log(f(A));

Upvotes: 4

ardenit
ardenit

Reputation: 3890

There is a solution in O(n^2 + S), where S is count of quadruples satisfying your condition.

  • Create a hash-based map M that maps integers to lists of pairs of integers (HashMap<Integer, List<Pair<Integer, Integer>>>).

  • For each pair (i, j) of indices (i < j) add this pair to list M[A[i] + A[j]]. (For-loop by j should be outer and for-loop by i should be nested, so pairs in all lists are sorted by j)

  • For each pair (k, l) of indices (k < l):

    • Let L be the list M[A[l] - A[k]]

    • For pairs (i, j) in L:

      • If j < k, add (i, j, k, l) to your answer

      • Else break nested loop, because pairs are sorted by j and following pairs will not satisfy condition j < k

Both outer loops run in O(n^2), nested loop runs only S times through the whole algorithm, so time complexity is O(n^2 + S).

Upvotes: 1

Related Questions