Given an array of integers (positive and negative numbers) and you have to find a triplet (3 elements) in array whose sum is equal to zero

OR

Find a triplet in an array whose sum is equal to a given input number. Find 3 elements from array whose sum is zero.

Example 1: Given array of integers is let

Input Array: 1, 5, 7, 3, 4, 2 and given number is 10
Output: Triplets whose sum is equal to given number 10 are

Triplets: 1 7 2
Triplets: 1 5 4
Triplets: 2 5 3

Example 2: Given array of integers positive and negatives are

Input Array: -1, 12, 5, 7, -2, -4, 5, 1 and given number is 11
Output: Triplets whose sum is equal to given number 11 are

Triplets: -2, 1, 12
Triplets: -1, 5, 7
Triplets: -1, 5, 7
Triplets: 1, 5, 5

Example 3: Given an array of integers find the triplet whose sum is zero

Input Array: -1, 12, 5, 7, -2, -4, 5, 1 and given number is 0 (zero)
Output: Triplets whose sum is equal to given number zero are

Triplets: -4, -1, 5

Method 1

Time Complexity: O(N2)
Space Complexity: O(1)

    1. Sort the given array first which will give us time complexity of (n log n)
    2. Take 3 pointers p1, p2, p3 where p1 is pointing to start of array, p2 will be pointing next to p1 and p3 will be pointing to last index of an array.
    3. Have a loop1 to move (Increment) p1 till p1 < p3
    4. For each iteration of loop1 have loop2 to move (Increment) p2 till p2 < p3
    5. If sum of Array[p1] + Array[p2] + Array[p3] > k then Decrement p3
    6. If sum of Array[p1] + Array[p2] + Array[p3] == k then Print the elements
    7. p2 = p1 +1 and p3 = Array.length – 1

Java Code for Method 1


import java.util.Arrays;

public class TripletsSumEqualtoNumber {

	public static void findTriplets(int arr[], int k)
	{
		Arrays.sort(arr);
		int p1=0, p2, p3, counter=0;
		p2 = p1 + 1;
		p3 = arr.length - 1;
		while(p1 < p3)
		{
			while(p2 < p3)
			{
				if((arr[p1] + arr[p2] + arr[p3]) > k)
					p3--;
				if(((arr[p1] + arr[p2] + arr[p3]) == k) && (p2 <= p3))
				{
					System.out.println("Triplets: " + arr[p1] + ", " + arr[p2] + ", " + arr[p3]);
					counter++;
				}
				p2++;
			}
			p1++;
			p2 = p1 + 1;
			p3 = arr.length - 1;
		}
		
		if(counter==0)
			System.out.println("No triplets found with sum equal to " + k);
	}
	
	public static void main(String[] args) {
		int arr[] = {1,5,7,3,4,2};
		//int arr[] = {-1,12,5,7,-2,-4,5,1};
		//int arr[] = {1,5,5,7,12};
		int k = 10;
		if(arr.length>2)
			findTriplets(arr,k);
	}
}

Try It

Method 2

Time Complexity: O(N2)
Space Complexity: O(1)

This is another program with he similar logic as Method 1. Here also we need to find the triplets from an array whose sum is equal to given number.

1. First sort the input array
2. Fix the first element as arr[i], where i ranges from 0 to N-2

a. 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 sorted array.

b. 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.

Triplet Sum Equal to Number

C++ Program for Method 2


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

int main()
{
	int arr[] = {18, 17, 8, 10, 19, 11, 12, 3, 4, 1, 6, 9}; //array
	int N = sizeof(arr)/sizeof(arr[0]);//size of array
	
	
	int X;
	cin>> X; //number to which a triplet should sum to
	
	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<<"No Such triplet exists\n";
	return 0;
}

Try It

 

Method 3

Time Complexity: O(N3)
Space Complexity: O(1)

We can make use of 3 loops to make all the combinations and find the 3 elements whose sum is equal to given number or zero

Java Code for Method 3


import java.util.Arrays;

public class TripletsSumEqualtoNumber {

	public static void findTriplets(int arr[], int sum)
	{
		int counter = 0;
		for (int i = 0; i < arr.length - 2; i++) { 

			for (int j = i + 1; j < arr.length - 1; j++) 
			{ 
				for (int k = j + 1; k < arr.length; k++) 
				{ 
					if (arr[i] + arr[j] + arr[k] == sum) 
					{ 
						System.out.println("Triplets: " + arr[i] + ", " + arr[j] + ", " + arr[k]);
						counter++;
					} 
				} 
			} 
		}
		
		if(counter==0)
			System.out.println("No triplets found with sum equal to " + sum);
	}
	
	public static void main(String[] args) {
		int arr[] = {1,5,7,3,4,2};
		//int arr[] = {-1,12,5,7,-2,-4,5,1};
		//int arr[] = {1,5,5,7,12};
		int k = 10;
		if(arr.length>2)
			findTriplets(arr,k);
	}
}

Try It

Conclusion

Obviously Method 1 is more efficient then Method 2. This is a commonly asked question in interviews. There are other possible ways which can be better than Method 2. If you can implement much better algorithm then post it here in comment section.

LEAVE A REPLY

Please enter your comment!
Please enter your name here