Home » Technical Interview Questions » Array Interview Questions » Find Triplet in Array With a Given Sum

Find Triplet in Array With a Given Sum


Reading Time - 2 mins

Given an array of integers, find the combination of three elements in the array whose sum is equal to a given value X. Here we will print the first combination that we get. If there is no such combination then print -1.

Example

Input

N=5, X=15

arr[] = {10, 4, 2, 3, 5}

Output 

10, 2, 3

Approach 1

Generating all the triplets and comparing the sum to the given value. The below algorithm contains three loops.

Algorithm

  1. First sort the input array
  2. Fix the first element as arr[i], where i ranges from 0 to N-2.
  3. After Fixing the first element, fix the second element as arr[j], where j ranges from  i+1 to N-1.
  4. After fixing the second element, fix the third element as arr[k], where k ranges from j+1 to N.
  5. Find the sum, arr[i] + arr[j] + arr[k].
  6. If the Triplet sum is equal to the value X, print the three elements else print -1.

C++ Program for Find Triplet in Array With a Given Sum

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N,X;//size of the array
    cin>>N>>X;
    int arr[N];
    for(int i=0;i<N;i++)
    {
        cin>>arr[i];
    }
    for(int i=0;i<N;i++)
    {
        for(int j=i+1;j<N;j++)
        {
            for(int k=j+1;k<N;k++)
            {
                if( arr[i] + arr[j] + arr[k] == X)
                {
                   cout << arr[i] <<"  "<<arr[j]<<"  "<<arr[k];
                   return 1;
                }
            }
        }
    }
    cout<<-1<<endl;
    return 0;
}
5 15
10 4 2 3 5
10  2  3

Approach 2

Algorithm

  1. First sort the input array
  2. Fix the first element as arr[i], where i ranges from 0 to N-2.
  3. After fixing the first element, for finding the next two elements, take two-pointer like variables ( j = i+1, k= N-1) and traverse the algorithm for finding the sum in a sorted array.
  4. While j is less than k Add the elements at the given indexes ie, arr[i] + arr[j] + arr[k] if Triplet sum is equal to the value X, print the three elements else if Triplet sum is less than the value X, then increase the j value else decrease the value of k.

C++ Program for Find Triplet in Array With a Given Sum

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N,X;//size of the array
    cin>>N>>X;
    int arr[N];
    for(int i=0;i<N;i++)
    {
        cin>>arr[i];
    }
    sort(arr,arr+N); //sort the array in ascending order
    int computed_sum;//sum computed at each step
  
    for(int i = 0; i < N - 2; i++) // fix one element and search for other two elements in linear time
    {
      int j = i+1 , k = N-1; // jth index starts from the next element of selected and k always starts at the ending index
      
      while(j < k)
      {
        computed_sum = arr[i] + arr[j] + arr[k]; // add the elements at the given indices
        
        if(computed_sum == X)
          {
            cout << arr[i] <<"  "<<arr[j]<<"  "<<arr[k];
            return 1;
          }
        else if(computed_sum < X) // means we need to increase some element but as i is fixed and k is already higher than i and j. We increment jth index
          j++;
          
        else if(computed_sum > X)//means we need to decrease some element but as i is fixed and j is already smaller than kth index element , we decrement k
          k--;
      }
    }
  cout<<-1<<endl;
    return 0;
}
5 15
1 4 2 3 5
-1

Complexity Analysis for Find Triplet in Array With a Given Sum

Time Complexity

O(n*n*n) where n is the number of elements present in the array. Here we Ron three for loop and check for every possible triplet.

READ  Peak Index in a Mountain Array

Space Complexity

O(1) because we don’t use any auxiliary space here.

References

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions