Sum of special triplets having elements from 3 arrays

Given three arrays A, B, and C, the task is to find sum of values of all special triplets. A special triplet is defined as a triplet (X, Y, Z) where the condition : 
X ? Y and Z ? Y always hold true. The value of each triplet (X, Y, Z) is given by: 

f(X, Y, Z) = (X + Y) * (Y + Z)

Note: If a triplet is not ‘special’, f(x, y, z) = 0 for that particular triplet.

Examples:  

Input : A = {1, 4, 5}, B = {2, 3}, C = {2, 1, 3}
Output : 81
Explanation
The special triplets and their values are given below
Triplet      f(x, y, z) = (x + y) * (y + z)
(1, 2, 2)         (1 + 2) * (2 + 2)  = 12
(1, 2, 1)         (1 + 2) * (2 + 1)  =  9
(1, 3, 2)         (1 + 3) * (3 + 2)  = 20
(1, 3, 1)         (1 + 3) * (3 + 1)  = 16
(1, 3, 3)         (1 + 3) * (3 + 3)  = 24
-------------------------------------
                           Sum = 81

Method 1 (Brute Force): We generate all triplets and check if a triplet is a special triplet, we calculate the value of the triplet using f(x, y, z) where (x, y, z) is a special triplet, and add it to the final sum of all such special triplets.

Implementation:

Sum of values of all special triplets = 81

The Time Complexity of this approach is O(P * Q * R) where P, Q, and R are the sizes of the three arrays A, B, and C respectively.

Method 2 (Efficient):

Suppose, 
Array A contains elements {a, b, c, d, e}, 
Array B contains elements {f, g, h, i} and 
Array C contains elements {j, k, l, m}.

First, we sort the arrays A and C so that we are able to find the number of elements in arrays A and C that are less than a particular B_i which can be done by applying binary search on each value of B_i.

Let’s suppose that at particular index i, the element of array B is B_i. Let’s also suppose that after we are done sorting A and C, we have elements {a, b, c} belonging to array A which are less than or equal to B_i and elements {j, k} belonging to array C which is also less than B_i. 

Lets take Bi = Y from here on.

Let, Total Sum of values of all special triplets = S 
We Know S = ? f(x, y, z) for all possible (x, y, z)

Since elements {a, b, c} of Array A and elements {j, k} of array C are less than Y,
the Special Triplets formed consists of triplets formed only using these elements 
with Y always being the second element of every possible triplet

All the Special Triplets and their corresponding values are shown below:

Triplet   f(x, y, z) = (x + y) * (y + z)
(a, Y, j)         (a + Y)(Y + j)  
(a, Y, k)         (a + Y)(Y + k)  
(b, Y, j)         (b + Y)(Y + j)  
(b, Y, k)         (b + Y)(Y + k)  
(c, Y, j)         (c + Y)(Y + j)  
(c, Y, k)         (c + Y)(Y + k)

The sum of these triplets is
S = (a + Y)(Y + j) + (a + Y)(Y + k) + (b + Y)(Y + j) + (b + Y)(Y + k) 
    + (c + Y)(Y + j) + (c + Y)(Y + k)

Taking (a + X), (b + X) and (c + x) as common terms we have,

S = (a + Y)(Y + j + Y + k) + (b + Y)(Y + j + Y + k) + (c + Y)(Y + j + Y + k)
Taking (2Y + j + k) common from every term,
S = (a + Y + b + Y + c + Y)(2Y + j + k)  

? S = (3Y + a + b + c)(2Y + j + k)

Thus,
S = (N * Y + S1) * (M * Y + S2) 
where, 
N = Number of elements in A less than Y,
M = Number of elements in C less than Y,
S1 = Sum of elements in A less than Y and
S2 = Sum of elements in C less than Y

So for every element in B, we can find the number of elements less than it in arrays A and C using Binary Search and the sum of these elements can be found using prefix sums  

Implementation:

Sum of values of all special triplets = 81

Since we need to iterate through the entire array B and for every element apply binary searches in array A and C, the Time Complexity of this approach is O(Q * (logP + logR)) where P, Q, and R are the sizes of the three arrays A, B, and C respectively.