Three number sum in an Array: Interview Question

November 10, 2020   100 interview questions , amazon questions , Array , array in data structure , interview questions , three sum

Problem Statement :

In three number sum problem, you have given an array of integers, you have to find the total sets of integers by adding them we can get our target sum.

Example 1

Input  :   array = {12,3,1,2,-6,5,-8,6}   target sum = 12
Output :   [-6 6 12 ] , [1 5 6 ] 

Example 2

Input  :   array = {2,3,1,4,-6,5,-1,6}   target sum = 8;
Output :   [-1 3 6 ] [-1 4 5 ] [1 2 5 ] [1 3 4 ] 

How to solve this problem

Method 1

A simplistic approach is to produce all possible sets of numbers and compare the sum of each set to our target sum. If it satisfies our condition then we insert that set of integers in our product array and proceed further till we will not iterate all elements.

Algorithm

1.  Given an array of length N and target sum T.
2. design three nested loop first loop runs from start to end (iterator i), the second loop runs from i+1 to end (iterator j) and the third loop runs from j+1 to end (iterator k).
3. The iterator of these loops denotes the index of 3 elements of the set of elements.
4. Find the sum of ith, jth, and kth element. If the sum is equal to the target sum. Insert the set of elements in our final array.
5. After completion return the output array. 

Complexity Analysis

Time complexity analysis: There exist three nested loops traversing the array, so the time complexity will be O(n3)
Space Complexity: No extra space is required O(1)

Implementation in C++

#include<iostream>
#include<vector>
using myvec=std::vector<int>;
 std::vector<myvec> three_Sum(myvec arr,int target)
 {
   myvec result;
    for (int i = 0; i < arr.size(); i++)
    { 
        for (int j = i + 1; j < arr.size(); j++)
        { 
            for (int k = j + 1; k <arr.size(); k++)
            { 
                if (A[i] + A[j] + A[k] == target)
                {
                 myvec temp={arr.at(i),arr.at(j),arr.at(k)};
                 result.push_back(temp);
                } 
            } 
        } 
    } 
 
    return result; 
} 
int main()
{
    myvec arr={2,3,1,4,-6,5,-1,6};
    int target=8;
    std::vector<myvec>output=three_Sum(arr,target);
    for(int i=0;i<output.size();i++){
       myvec temp=output.at(i);
       std::cout<<"[";
       for(int j=0;j<temp.size();j++){
           std::cout<<temp.at(j)<<" ";
       }
        std::cout<<"] ";

    }
    return 0;
}
// You can use this code for educational purpose only
//( copyright coderca 2020)

Method 2

By Sorting the array the effectiveness of the algorithm can be increased. This effective procedure uses the two pointers to solve this particular problem. Traverse the array and set the first element of the set. Now set the first pointer to i+1 and the second pointer to n-1. to find if there is a pair whose sum is equal to targetSum – array[i]. If there is then add the set of (i, left, right ) to our output array.

Algorithm

1. Sort the given array.
2. iterate the array and fix the first element to the arr[i].
3.  Then fix two pointers, left to i + 1 and the right to n – 1. And look at the sum of ( arr[i], arr[left], arr[right].
4.  If the sum equals the target sum then insert the set into our output array.
   •  increase left by 1 and decrease right by 1.
5. Else, If the sum is bigger than the target sum, Decrease the right by 1;
6.  Else, if the sum is smaller than the target sum, increase the left by 1;
7.  do 3,4,5,6 while the left is smaller than right.
8. return the output array.

Complexity Analysis

Time complexity analysis: It takes O(nlogn) time to sort and There exist two nested loops traversing the array, so the time complexity will be O(n2)
Space Complexity: No extra space is required O(1)

Implementation in C++

// three number sum equals to a target problem 
// time-complexity =O(N^2)
// space-complexity=O(N)
#include<iostream>
#include<thread>
#include<vector>
#include<algorithm>
using myvec=std::vector<int>;
 std::vector<myvec> three_Sum(myvec arr,int target)
 {
     std::vector<myvec> result;
     std::sort(arr.begin(),arr.end());
     for(int i=0;i<arr.size();i++){
         int left=i+1;
         int right=arr.size()-1;
         while (left!=right && left<right)
         {
             if(arr.at(left)+arr.at(right)+arr.at(i)==target)
             {
                myvec temp={arr.at(i),arr.at(left),arr.at(right)};
                result.push_back(temp);
                left=left+1;
                right=right-1;
             }
             else if(arr.at(left)+arr.at(right)+arr.at(i)<target)
             {
                left=left+1;
             }
             else if(arr.at(left)+arr.at(right)+arr.at(i)>target)
             {
                right=right-1;
             }
         }

     }
     return result;
 }
int main()
{
    myvec arr={2,3,1,4,-6,5,-1,6};
    int target=8;
    std::vector<myvec>output=three_Sum(arr,target);
    for(int i=0;i<output.size();i++){
       myvec temp=output.at(i);
       std::cout<<"[";
       for(int j=0;j<temp.size();j++){
           std::cout<<temp.at(j)<<" ";
       }
        std::cout<<"] ";

    }
    return 0;
}
// You can use this code for educational purpose only
// ( copyright coderca 2020)