Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Example 
2.
Brute Force Approach
2.1.
Algorithm
2.2.
Implementation
2.2.1.
Complexity Analysis
3.
Optimized Approach
3.1.
Algorithm
3.2.
Implementation
3.2.1.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
What is a two-pointer approach?
4.2.
What is a set?
4.3.
What is the use of sort function in the approach?
5.
Conclusion
Last Updated: Mar 27, 2024

All Unique Triplets that Sum up to a Given Value

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

This blog will discuss the approach to finding all the unique triplets that sum up to a given value. Before jumping on the approach to the problem, let us first understand the problem.

All Unique Triplets that Sum up to a Given Value

Problem Statement

Given an array, we have to find and print all the unique triplets whose sum equals the given value. Note that all the triplets should be unique. In case no such triplets are possible, return an empty array.

For example, (3,5,5) and (5,3,5) should be considered the same, and only one should be returned.

Sample Example 

Input : array = {15,5,10,5,10} sum = 25

Array Example

Output : [ [15,5,5], [5,10,5] ]

Since 15 + 5 + 5 = 25 and 5 + 10 + 5 = 25, therefore the unique triplets are [15,5,5] and [5,10,5].

Input : array = {-3,0,2,3,-2} sum = 0

Array Example

Output : [ [-3,0,3], [2,0,-2] ]

Since 0 + 2 + (-2) = 0 and (-3) + 0 + 3 = 0, therefore the unique triplets are [-3,0,3] and [2,0,-2].

Brute Force Approach

In this approach,we basically need to find three indexes which satisfy the condition A[i] + A[j] + A[k] = given sum. We do this by fixing the first index and iterating the other two indexes as a two-pointer system. In order to maintain the uniqueness of the triplets, a set will be used.

Algorithm

Step 1: Sort the input array

Step 2: Find three index i,j,k such that A[i]+A[j]+A[k] = sum given

Step 3: Fix the first index i and let i iterate from 0 to array size - 2.

Step 4: For each iteration of i, take j to be the index of the middle element and k to be the index of the last element.

Step 5: check the following equation, A[i] + A[j] + A[k] = given sum.

Step 6: If the above equation is satisfied,then

  • Add the triplet in the set
  • Increment the mid index
  • Decrement the third index
  • Repeat step 4 & 5 till j < k

Step 7: Else if,A[i] + A[j] + A[k] > given sum, Increment the mid index.

Else, if A[i] + A[j] + A[k] < the given sum,Decrement the last index.

Implementation

C++

using namespace std;
 
// Structure to define a triplet.
struct triplet
{
    int first, second, third;
};
 
vector<triplet> findTriplets(int nums[], int n, int sum)
{
    int i, j, k;
 
    // Vector to store all unique triplets.
    vector<triplet> triplets;
 
    //unordered Set to store already found triplets
    // to avoid duplication.
    unordered_set<string> uniqueTriplets;
 
    // Variable used to hold triplet
    // converted to string form.
    string temp;
 
    triplet newTriplet;
 
    sort(nums, nums + n);
 
    for (i = 0; i < n - 2; i++)
    {
        // index of the first element in
        // the remaining elements.
        j = i + 1;
 
        // index of the last element.
        k = n - 1;
 
        while (j < k) {
 
            
            if (nums[i] + nums[j] + nums[k] == sum)
            {
                temp = to_string(nums[i]) + " : "
                      + to_string(nums[j]) + " : "
                      + to_string(nums[k]);
                if (uniqueTriplets.find(temp)
                    == uniqueTriplets.end()) {
                    uniqueTriplets.insert(temp);
                    newTriplet.first = nums[i];
                    newTriplet.second = nums[j];
                    newTriplet.third = nums[k];
                    triplets.push_back(newTriplet);
                }

                j++;
                k--;
            }
 
            
            else if (nums[i] + nums[j] + nums[k] > sum)
                k--;
 
            else
                j++;
        }
    }
 
  return triplets;
}
 
// Driver Code
int main()
{
    int nums[] = {15,5,10,5,10};
    int n = sizeof(nums) / sizeof(nums[0]);
    int sum = 25;
  
    // Function call
    vector<triplet> result = findTriplets(nums, n, sum))
    if( result.size() == 0 )
    cout<<”No such triplet possible”<<endl;
      // Print all unique triplets stored in
    // vector.
    for (i = 0; i < result.size(); i++) {
        cout << "[" << result[i].first << ", "
            << result[i].second << ", "
            << result[i].third << "], ";
    }
 
    return 0;
}

Output : 

[ [ 15,5,5 ],[ 5,10,10 ] ]

Complexity Analysis

Time complexity: O( n^2 )

Since there are n traversals in total and each traversal costs O(n) time,therefore total time required would be of order O(n^2).

Space complexity: O( n )

As an unordered set is used therefore space complexity is of order O(n).

Also see, Rabin Karp Algorithm

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Optimized Approach

In this approach, a constant space complexity approach is discussed. We will do so by checking if the previous element is the same as the current one. If so, we will skip this value and iterate to the next one. By using this algorithm, we will be getting only unique triplets that satisfy the equation.

Algorithm

Step 1: Sort the input array

Step 2: Fix the first index i and let i iterate from 0 to array size - 2.

Step 3: For each iteration of i, take j to be the index of the middle element and k be the index of the last element.

Step 4: In this, we will look for the previous elements. If they are the same, then we will skip.

Step 5: check the following equation, A[i] + A[j] + A[k] = given sum.

Step 6: If the above equation is satisfied,then

  • Add the triplet in the set
  • Increment the mid index
  • Decrement the third index
  • Repeat step 4 & 5 till j < k

Step 7: Else if,A[i] + A[j] + A[k] > given sum, Increment the mid index.

Else if,A[i] + A[j] + A[k] <the given sum,Decrement the last index.

Implementation

c++

//Brute force method to find all unique triplets.
#include <bits/stdc++.h>
using namespace std;
//function to find all unique triplets
vector<vector<int>> findTriplets(int arr[], int n, int sum){
sort( arr , arr + n );
//A 2D vector to store the result.
      vector<vector<int>> result;
for( int i = 0 ; i< n -2 ; i++ ){
int start = i+1;
int end = n-1;
            //calculating new target sum after subtracting the fixed one from the old target.
int new_target = sum - arr[ i ];
while( start < end ){
            //checking if previous value is same as current value.
      if (start > i + 1
                    && arr[start] == arr[start - 1])
                {
                    start++;
                    continue;
                }
          if (end < n - 1
                    && arr[end] == arr[end + 1])
                {
                    end--;
                    continue;
                }
                //if the sum is equal to the target then push it into the result.
          if(new_target == arr[start ] + arr[ end ]){
    result.push_back( {arr[i],arr[start],arr[end] } );
    Start++;
    end--;
                }
                Else if( new_target > arr[start] + arr[end]){
          start++;
                }
                Else{
          end--;
                }
            }
            }
          return result;
}
int main(){

      int arr[] = {15,5,10,5,10};

      int n = sizeof(arr)/sizeof(a[0]);

      int sum = 25;

      //2D vector to store the result.

      vector<vector<int>> result =  findTriplets(arr, n, sum);

      if(result.size() == 0)

      cout<<”No such triplet exists”<<endl;

      for(int i = 0;i<result.size();i++){

           cout<<result[i][0]<<” ”<<result[i][1]<<” ”<<result[i][2]<<endl; 

      }

      return 0;

}

Output :

 [ [ 15,5,5 ],[ 5,10,10 ] ]

Complexity Analysis

Time complexity : O( n^2 )

Since there are n traversals in total and each traversal costs O(n) time,therefore total time required would be of order O(n^2).

Space complexity : O( 1 )

As no extra space is required apart from the given array,therefore total space complexity is of order O(1).

Check out this problem - Two Sum Problem

Frequently Asked Questions

What is a two-pointer approach?

Two Pointers is a pattern in which the two pointers iterate across the data structure until one or both of them satisfy the necessary condition. For more details, click here.

What is a set?

Sets are containers that store unique elements. A stored element must be unique because it is identified with the value itself. Once the elements are inserted in the set, they cannot be modified; however, they can be inserted or removed from the container.

What is the use of sort function in the approach?

It is the sort function that sorts the array in O(nlogn), which in turn provides the flexibility to place our two pointers in start and end and move to left and right.

Conclusion

This article discussed different approaches to finding all the unique triplets that sum to a given value. First, a method is discussed which uses O(n) space and the second approach is the optimization over the first approach, which does the task in O(1) space.

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem DesignMachine learning and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!!

Thankyou
Previous article
Count the number of possible triangles
Next article
Sorting all array elements except one
Live masterclass