Reading time: 25 minutes | Coding time: 20 minutes

In this article, we have explored insightful approaches / algorithms to find elements in 4 arrays whose sum is equal to zero. This is an extension of 4 SUM PROBLEM.

CONTENTS OF THE ARTICLE:

• Pre-requisites
• Problem Statement Definition
• Solution Analysis
• Method 1: Naive approach
• Method 2: Applied Binary Search
• Method 3: Sorting and Two-pointer approach
• Method 4: Extended two-pointer approach
• Method 5: Hashing Based Solution
• Applications

PRE-REQUISITES

• Binary Search
• Sorting
• Two-pointer technique
• Hash-maps
• 4 SUM PROBLEM

This problem is similar to Leetcode problem 454. 4Sum II.

PROBLEM STATEMENT DEFINITION

Given an 4 arrays, each containing n integers, we have to find four elements a (from array-1), b (from array-2), c (from array-4), and d (from array 4) such that a + b + c + d = 0. We need to find all unique quadruplets among the arrays which gives the sum of zero.

Note: The solution set must not contain duplicate quadruplets.

Example

Input:

• n = 5
• a1= [12, 5, -1, 0, -2],
• a2= [-11, 5, 9, 10, 3],
• a3= [7, 10, -1, 0, -88],
• a4= [100, 101, 102, 0, -101]

Output:

• [12, -11, -1, 0]
• [-1, -11, -88, 100]
• [-2, -11, -88, 101]
• [-2, 3, -1, 0]

Explanation:

• 12 (from array-1) + -11 (from array-2) + -1 (from array-4) + 0 (from array 4) = 0
• -1 (from array-1) + -11 (from array-2) + -88 (from array-4) + 100 (from array 4) = 0
• -2 (from array-1) + -11 (from array-2) + -88 (from array-4) + 101 (from array 4) = 0
• -2 (from array-1) + 3 (from array-2) + -1 (from array-4) + 0 (from array 4) = 0

SOLUTION ANALYSIS

• Intuitively the most basic way of solving would be to check each and every possible combination
• The second approach would be to compute the sum of three elements and find its additive inverse in the fourth array
• Another approach would be to search the third and fourth array simultaneously for a sum that added with the computed sum from the first two arrays is equal to zero.
• The final approach would be to use a hash-map for efficient searching.

All the above-mentioned approaches are discussed in the following article!

METHOD-1 NAIVE APPROACH

A Naive Solution is to generate all possible quadruples and compare the sum of every quadruple with 0. The following code implements this simple method using four nested loops

ALGORITHM

• Given 4 arrays of length n
• Create four nested loop first loop (loop counter i), second loop (loop counter j), third loop (loop counter k), fourth loop (loop counter l). All four loops have n iterations ( from 0 to n)
• The counter of these loops represents the index of 4 elements of the quadruple.
• Find the sum of ith, jth, kth and lth element and compare it with 0
• If it is equal, print the quadruple set and check for other solution sets

IMPLEMENTATION

Let us have a look at the C++ program for the problem

#include <bits/stdc++.h>
using namespace std; 

void Naive_4SUM(int A1[], int A2[], int A3[], int A4[], int n)
{
int S = 0;     
// Select the first element and find other three
for (int i = 0; i < n; i++)
{
    // Select the second element and find other two
    for (int j = 0; i < j; j++)
    {
         
        // Select the third element and find the fourth
        for (int k = 0; k < n; k++)
        {
            // Find the fourth element
            for (int l = 0; l < n; l++)
            if (A1[i] + A2[j] + A3[k] + A4[l] == S) //Comparing the sum with S = 0
                cout << "["<<A1[i] <<", " << A2[j]<< ", " << A3[k] << ", " << A4[l]<<"]"<<endl;
        }
    }
}
}
 

int main()
{
    int a1[]= {12, 5, -1, 0, -2}, a2[]= {-11, 5, 9, 10, 3}, a3[]= {7, 10, -1, 0, -88}, a4= {100, 101, 102, 0, -101}
    int n = 5;
    int target = 23;
    Naive_4SUM(a1, a2, a3, a4, n);
    return 0;
}

OUTPUT
[12, -11, -1, 0]
[-1, -11, -88, 100]
[-2, -11, -88, 101]
[-2, 3, -1, 0]

Time-Complexity

It can be easily seen that the complexity is n^4 (since we have four nested loops). The complexity can be decreased if we want just one quadruple set but since we want all possible sets we have to settle for an inefficient n^4

• Worst case time complexity: Θ(n^4)
• Average case time complexity: Θ(n^4)
• Best case time complexity: Θ(n^4)

Space-Complexity

We do not use any other extra space. Hence the Space complexity is Θ(1)

METHOD-2 APPLIED BINARY SEARCH

The idea is to find to compute the sum of elements of three arrays naively and then use binary search to find its additive inverse.

ALGORITHM

• Apply 3 nested loops for the first three arrays.
• Generate all triplets from the 1st three arrays. For each triplet so generated, find the sum of elements in the triplet. Let it be T.
• Now, search the value (x – T) in the 4th array.
• If the value found in the 4th array, then print the quadruple.
• This process is repeated for all the triplets generated from the 1st three arrays.

IMPLEMENTATION

C++ Program

#include <bits/stdc++.h>
 
using namespace std;
void BS_4SUM(int arr1[], int arr2[], int arr3[],int arr4[], int n);
int isPresent(int arr[], int low, int high, int value);

int main()
{
    int a1[]= {12, 5, -1, 0, -2}, a2[]= {-11, 5, 9, 10, 3}, a3[]= {7, 10, -1, 0, -88}, a4[]= {100, 101, 102, 0, -101};
    int n = 5;
    BS_4SUM(a1, a2, a3, a4, n);
    return 0;
}

int isPresent(int arr[], int low, int high, int value)
{
    while (low <= high) {
        int mid = (low + high) / 2;
 
        // 'value' found
        if (arr[mid] == value)
            return arr[mid];
        else if (arr[mid] > value)
            high = mid - 1;
        else
            low = mid + 1;
    }
 
    return -100000000; //flag value
}
 

void BS_4SUM(int arr1[], int arr2[], int arr3[],int arr4[], int n)
{
    int x = 0;
    // generate all triplets from the 1st three arrays
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            for (int k = 0; k < n; k++) {
 
                // calculate the sum of elements in
                // the triplet so generated
                int T = arr1[i] + arr2[j] + arr3[k];
 
                // check if 'x-T' is present in 4th
                // array or not
                if (isPresent(arr4, 0, n, x - T)!=-100000000)
                    cout << "["<<arr1[i] <<", " << arr2[j]<< ", " << arr3[k] << ", " << isPresent(arr4, 0, n, x - T)<<"]"<<endl;
            }
}

OUTPUT
[12, -11, -1, 0]
[-1, -11, -88, 100]
[-2, -11, -88, 101]
[-2, 3, -1, 0]

Time-Complexity

It can be easily seen that the complexity is n^3 (since we have 3 nested loops) multiplied with the time for binary search (log n). The complexity can be decreased if we want just one quadruple set!

• Worst case time complexity: Θ(n^3 * log n)
• Average case time complexity: Θ(n^3 * log n)
• Best case time complexity: Θ(n^3 * log n)

Space-Complexity

We do not use any other extra space. Hence the Space complexity is Θ(1)

METHOD-3 SORTING AND TWO POINTER APPROACH

The time complexity of the above algorithm can be improved to O(n^3) with the use of sorting as a preprocessing step, and then using method 1 of this article to reduce one loop implementation.

ALGORITHM

• Sort all the arrays in time O(n * log n).
• Set two nested arrays for array1 and array 2
• Set two pointers left — k = 0 and right — l = n .
• Check if a1[i] + a2[j] + a3[k] + a4[l] == 0 and add it to the result, if true.
• If a1[i] + a2[j] + a3[k] + a4[l] < target, then we are too left, and we need to move right so increment left pointer i.e. k++.
• If a1[i] + a2[j] + a3[k] + a4[l] > target, then we are too right, and we need to decrement the right pointer i.e., l--.

IMPLEMENTATION

#include <bits/stdc++.h>
using namespace std;

 
int two_pointer_4SUM(int arr1[], int arr2[], int arr3[], int arr4[], int n);
int Pairwise(int arr1[], int arr2[], int n, int value);


int main()
{
    int a1[]= {12, 5, -1, 0, -2}, a2[]= {-11, 5, 9, 10, 3}, a3[]= {7, 10, -1, 0, -88}, a4[]= {100, 101, 102, 0, -101};
    int n = 5;
    cout << "Number of unique solutions= "<< two_pointer_4SUM(a1, a2, a3, a4, n);
    return 0;
}

int Pairwise(int arr1[], int arr2[], int n, int value)
{
    int count = 0;
    int l = 0, r = n - 1;
    while (l < n  and r >= 0) {
        int sum = arr1[l] + arr2[r];
        if (sum == value) {
            l++, r--;
            count++;
        }
        else if (sum > value)
            r--;
        else
            l++;
    }
 
    return count;
}

int two_pointer_4SUM(int arr1[], int arr2[], int arr3[], int arr4[], int n)
{
    int count = 0, x=0;
    
    sort(arr1,arr1+n);
    sort(arr2,arr2+n);
    sort(arr3,arr3+n);
    sort(arr4,arr4+n);
    
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            int p_sum = arr1[i] + arr2[j];
            count += Pairwise(arr3, arr4, n, x - p_sum);
        }
    return count;
}

OUTPUT:
Number of unique solutions= 4

Time-Complexity analysis

We are scanning the entire first array keeping one element fixed and then doing it for another array. Thus, we are scanning each element of array n number of times. And we repeat this step n times, hence the worst case time complexity will be O(n3 + n * log n) which comes down to O(n3). Hence we can write the worst-case, average-case and best-case time complexities as:

• Worst case time complexity: Θ(n^3)
• Average case time complexity: Θ(n^3)
• Best case time complexity: Θ(n^3)

Space-Complexity analysis

We are not using any data structure for the intermediate computations, hence the space complexity is O(1).

• Space complexity: Θ(1)

METHOD-4 EXTENDED TWO POINTER APPROACH

This approach is an extension of the above method where we print the solution set as well. This algorithm has been modified to give only one unique set after which the program terminates. It can be removed by deleting the exit() system call.

Although this algorithm returns the answer for almost all general cases, there are some unique or bottleneck cases where it fails. It is used however because it is easy to implement and is efficient!

ALGORITHM

• Sort all the arrays in time O(n * log n).
• Set two nested arrays for array1 and array 2
• Set two pointers left — k = 0 and right — l = n .
• Check if a1[i] + a2[j] + a3[k] + a4[l] == 0 and print the set, if true.
• If a1[i] + a2[j] + a3[k] + a4[l] < target, then we are too left, and we need to move right so increment left pointer i.e. k++.
• If a1[i] + a2[j] + a3[k] + a4[l] > target, then we are too right, and we need to decrement the right pointer i.e., l--.

IMPLEMENTATION

Python Function for the same algorithm

def fourSum(a1: List[int], a2: List[int], a3: List[int], a4: List[int],target: int) -> List[List[int]]:
    # Resultant list
    quadruplets = list()
    # Sort the array
    a3.sort()
    a4.sort
    # Length of the array
    n = len(a1)
    # Loop for each element of the array
    for i in range(0, n - 3):
        # Check for skipping duplicates
        if i > 0 and a1[i] == a2[i]:
            continue
        # Reducing to three sum problem
        for j in range(i, n):
            # Check for skipping duplicates
            # Left and right pointers
            k = j + 1
            l = n - 1
            # Reducing to two sum problem
            while k < l:
                current_sum = a1[i] + a2[j] + a3[k] + a4[l]
                if current_sum < 0:
                    k += 1
                elif current_sum > 0:
                    l -= 1
                else:
                    quadruplets.append([a1[i], a2[j], a3[k], a4[l]])
                    k += 1
                    l -= 1
                    while k < l and a3[k] == a3[k - 1]:
                        k += 1
                    while k < l and a4[l] == a4[l + 1]:
                        l -= 1
    return quadruplets

#include<bits/stdc++.h>
using namespace std;
 
void SORT_4SUM(int a1[], int a2[], int a3[], int a4[], int n)
{
    int l, r;
    
    //Using library function sort
    sort(a1, a1+n);
    sort(a2, a2+n);
    sort(a3, a3+n);
    sort(a4, a4+n);
 
    
    for (int i = 0; i < n ; i++)
    {
        for (int j = 0; j < n; j++)
        {
            // Initialize two variables as indexes of the first and last elements in the remaining elements
            l = 0;
            r = n-1;
 
            
            while (l < r)
            {
                if( a1[i] + a2[j] + a3[l] + a4[r] == 0)
                {
                    cout <<"["<< a1[i]<<", " << a2[j] <<
                        ", " << a3[l] << ", " << a4[r]<<"]"<<endl;
                    l++; r--;
                    exit(0);
                }
                else if (a1[i] + a2[j] + a3[l] + a4[r] < 0)
                    l++;
                else // nums[i] + nums[j] + nums[l] + nums[r] > X
                    r--;
            } 
        } 
    }
}
 

int main()
{
    int a1[]= {12, 5, -1, 0, -2}, a2[]= {-11, 5, 9, 10, 3}, a3[]= {7, 10, -1, 0, -88}, a4[]= {100, 101, 102, 0, -101};
    int n = 5;
    SORT_4SUM(a1, a2, a3, a4, n);
    return 0;
}

OUTPUT
[-2, -11, -88, 101]

Time-Complexity analysis

We are scanning the entire first array keeping one element fixed and then doing it for another array. Thus, we are scanning each element of array n number of times. And we repeat this step n times, hence the worst case time complexity will be O(n3 + n * log n) which comes down to O(n3). Hence we can write the worst-case, average-case and best-case time complexities as:

• Worst case time complexity: Θ(n^3)
• Average case time complexity: Θ(n^3)
• Best case time complexity: Θ(n^3)

Space-Complexity analysis

We are not using any data structure for the intermediate computations, hence the space complexity is O(1).

• Space complexity: Θ(1)

METHOD-5 HASHING

APPROACH EXPLANATION

The idea is to consider every pair of elements in the array one by one and insert it into a hash table. For each pair of elements (i,j), calculate the remaining sum. If the remaining sum exists in the map and elements involved in the previous occurrence does not overlap with the current pair, i.e, (i,j,i,y) or (i,j,x,i) or (i,j,j,y) or (i,j,x,j), print the quadruplet and return

NOTE: This algorithm only gives the count of the number of unique quadruplets satisfying the criteria!

ALGORITHM

• Using two nested loops, create a hash-table using unordered-maps where (key, value) tuples are represented as (sum, frequency) tuples.
• Here the sum are obtained from the pairs of 1st and 2nd array and their frequency count is maintained in the hash table.
• Repeat the above steps for all four arrays considering two as a pair
• For each pair so generated, find the sum of elements in the pair.Let it be sum_pair. For each sum_pair, check whether (-1* sum_pair) exists in the hash table or not. If it exists, then add the frequency of (a-* sum_pair) to the count of quadruples.

IMPLEMENTATION

1. Python Implementation

def HASH_4SUM_array(arr1, arr2, arr3, arr4, n):
    count = 0
    
    m = {}
     
    # count frequency of each sum obtained from the
    # pairs of arr1[] and arr2[] and store them in 'um'
    for i in range(n):
        for j in range(n):
            if (arr1[i] + arr2[j]) in m:
                m[arr1[i] + arr2[j]] += 1
            else:
                m[arr1[i] + arr2[j]] = 1
     
    # generate pair from arr3[] and arr4[]
    for k in range(n):
        for l in range(n):
            sum_pair = arr3[k] + arr4[l]
            if (x - p_sum) in m:
                count += m[-1 * sum_pair]
     
    # required count of quadruples
    return count
 

a1 = [12, 5, -1, 0, -2]
a2= [-11, 5, 9, 10, 3]
a3= {7, 10, -1, 0, -88]
a4= [100, 101, 102, 0, -101]; 
n = 5 

print("Number of unique solutions: ", HASH_4SUM_array(a1, a2, a3, a4, n))

2. JAVA implementation

import java.util.*;
 
class array_4_SUM
{
static int HASH_4SUM_array(int arr1[], int arr2[], int arr3[], int arr4[], int n)
{
    int count = 0;
 
    Map<Integer,Integer> m = new HashMap<>();
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if(m.containsKey(arr1[i] + arr2[j]))
                m.put((arr1[i] + arr2[j]), m.get((arr1[i] + arr2[j]))+1);
            else
                m.put((arr1[i] + arr2[j]), 1);
                 
    for (int k = 0; k < n; k++)
        for (int l = 0; l < n; l++)
        {
            int sum_pair = arr3[k] + arr4[l];
 
            if (m.containsKey(-1 *p_sum))
                count += m.get(-1 * p_sum);
        }
    return count;
}

public static void main(String[] args)
{
    
    int a1[]= {12, 5, -1, 0, -2};
    int a2[]= {-11, 5, 9, 10, 3};
    int a3[]= {7, 10, -1, 0, -88};
    int a4[]= {100, 101, 102, 0, -101};
 
    int n = 5;
    System.out.println("Number of unique solutions: "
        + HASH_4SUM_array(a1, a2, a3, a4, n));
}
}

3. C++ Implementation

#include <bits/stdc++.h> 
using namespace std;
int HASH_4SUM_array(int arr1[], int arr2[], int arr3[],int arr4[], int n)
{
    int count = 0;
    unordered_map<int, int> um;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            um[arr1[i] + arr2[j]]++;
    for (int k = 0; k < n; k++)
        for (int l = 0; l < n; l++) {
            int sum_pair = arr3[k] + arr4[l];
            if (um.find(-1* sum_pair) != um.end())
                count += um[-1* sum_pair];
        }
    return count;
}
 

int main()
{
    int a1[]= {12, 5, -1, 0, -2};
    int a2[]= {-11, 5, 9, 10, 3};
    int a3[]= {7, 10, -1, 0, -88};
    int a4[]= {100, 101, 102, 0, -101};
    int n=5;
    cout << "Number of unique solutions: "
         << HASH_4SUM_array(a1, a2, a3, a4, n);
    return 0;
}

OUTPUT
Number of unique solutions: 4

Time-Complexity analysis

We only use two nested arrays to insert pairs of first two arrays into the hash-table. We use two nested loops to find the sum of the third and fourth array elements. We search the hash-table for its additive inverse in constant time

Therefore the time-complexity is:

• Worst case time complexity: Θ(n^2)
• Average case time complexity: Θ(n^2)
• Best case time complexity: Θ(n^2)

Space-Complexity Analysis

We use an auxiliary space of n^2 for the hash-table (each element of array-1 forms a pair with each element of array-2). Hence the Space complexity is Θ(n^2)

APPLICATIONS

• This problem is the most basic of a class of algorithms developed by Howgrave-Graham and Joux
• A variation of this problem is used in various other problems like convolution
• It finds many uses in computational geometry

With this article at OpenGenus, you must have the complete idea of solving 4 ARRAY SUM EQUAL TO ZERO efficiently!