Triplet Sum in Array

Problem Statement

An array of integers and a target sum are given, find out if there is any triplet whose sum is equal to the given target sum exists in the array or not, print the triplet, if a triplet sum in array is present and return true. Otherwise, return false.

Example

Input-1

Output-1

Explanation

Within the array, there is a triplet (1, 3, and 5) whose sum is 9.

Input-2

Output-2

Explanation

There is no triplet sum in array that exists in the array which has a sum equal to given target 5.

Constraints

Approach 1- Naive Approach

Intuition:

The simple approach to the above mentioned problem is to generate all the possible triplets and compare each triplet's sum to the given value. The below algorithm implements this naive approach of triplet sum in array using three nested loops.

Algorithm

1. A sum "target" and an array of length n are given.
2. Construct three nested for loops, where first loop counter i runs from arr[0] to end, where i ranges from 0 to N.
3. Second loop counter j runs from arr[1] to end, where i ranges from i+1 to N.
4. Third loop counter k runs from arr[2] to end, where i ranges from i+2 to N.
5. Find the sum of the ith, jth, and kth elements. if the sum matches the given target. Print the values and break from the loop.
6. Otherwise return false, if no triplet was found.

Code Implementation

Code in C++

Code in Java

Code in Python

Output

Time Complexity

The time complexity is O(n^3). Since there are three nested loops that traverse the array.

Space Complexity

The space complexity is O(1). Since no extra space is used in the solution of triplet sum in array.

Approach 2- Using Recursion

Intuition:

Recursion is used in this solution, and the concept is similar to the 0-1 Knapsack problem. For each item, we either consider the current number or leave it out and repeat for the remaining numbers. If we include or exclude the current item and we get the desired sum, return true.

Algorithm

1. Create a recursive function to check if a triplet sum in array exists with the given sum.
2. The recursion function takes an array, array length, target sum, and current count for the triplet.
3. Check if the triplet has the desired sum, If yes return true.
4. Otherwise, return false if the sum is negative with the current conditions.
5. At last, return the recursion function with two conditions (including and excluding the current number).

Code Implementation

Code in C++

Code in Java

Code in Python

Output

Time Complexity

The time complexity is O(3^n). Since we need three numbers in a triplet, the Base condition will hit for each number.

Space Complexity

The space complexity is O(N). Since recursion takes more memory for constants to find triplet sum in array.

Approach 3- Hashing-Based Solution - Using HashSet

Intuition:

Run the inner loop from position i+1 to position n, then the outer loop from start to end. Create a HashSet and store the elements from i+1 to j-1 in it. Check to see whether there is a number in the set that equals target - arr[i] - arr[j] if the given sum is the target.

Algorithm

1. From start to end, go through all the array elements with loop counter i.
2. Create a HashSet to store the unique pairs.
3. Run the second for loop from position i+1 until the end of the array.
4. If there is any number exists in the Hashset which is equal to target- arr[i] – arr[j], then print the triplet (arr[i], arr[j], target-arr[i]-arr[j]) and break from the loop.
5. Put the jth element in the HashSet.

Code Implementation

Code in C++

Code in Java

Code in Python

Output

Time Complexity

The time complexity is O(n^2). Since there are two nested loops that traverse the array.

Space Complexity

The space complexity is O(N). Since extra space is used in the solution as HashSet.

Approach 4- Efficient Approach - Using Two-Pointer Technique

Intuition:

The array can be sorted to increase the algorithm's efficiency. The Two-pointer Technique is used in this effective approach for triplet sum in array. Traverse the array and fix the triplet's first element. Now find a pair whose sum is equal to target - arr[i] by using the Two Pointers technique.

Algorithm

1. Sort the input array of integers.
2. Fix the first number of the possible triplet, arr[i], by iterating through the array.
3. Then, fix the two pointers, one at index i + 1 and the other at index i – 1. Now look for the sum.
4. Increase the first pointer if the sum is less than the required sum.
5. Else, Reduce the end pointer if the sum is higher to decrease it.
6. Otherwise, print the triplet and break from the loop if the sum of the numbers at the two-pointer equals the given target.

Code Implementation

Code in C++

Code in Java

Code in Python

Output

Time Complexity

The time complexity is O(n^2). Since there are two nested loops that traverse the array.

Space Complexity

The space complexity is O(1). Since no extra space is used in the solution of triplet sum in array.

Approach 5- Printing Distinct Triplets

Intuition:

The approach is to sort the input array in a non decreasing order and check whether a triplet is generated by an element from the array nums[i] and two pairs from nums[i+1....n] for each element in the array nums[i]. The Below implementation of code in Java, C++, and Python shows this intuition.

Algorithm

1. Sort the given array in ascending order.
2. Check if triplet is formed by nums[i] and a pair from subarray nums[i+1…n].
3. Maintain two indices pointing to endpoints of the subarray nums[i+1…n].
4. Construct a while loop if low is less than high.
   • increase the low index if the total is smaller than the remaining sum.
   • decrease the high index if the total is larger than the remaining sum.
5. Print the triplet, if the given target is found.

Code Implementation

Code in C++

Code in Java

Code in Python

Output

Time Complexity

The time complexity is O(n^2). Since there are three nested loops that traverse the array.

Space Complexity

The space complexity is O(1). Since no extra space is used in the solution for triplet sum in array.