Triplet Sum in Array

Last Updated on June 8, 2023 by Mayank Dham

In this post, we’ll examine one of the most significant problems in terms of both coding-based interviews and programming ideas. We’ll start by outlining the problem statement, then deconstruct it by talking about the dry run approach and examining the various methods we might use to write the code.

What is Triplet Sum in Array

As the name implies, a triplet sum combines the three separate elements from a triplet and adds them up in an array. To verify if any triplet in an array adds up to be equal to the input integer, an array, and an input integer are both provided.

There needs to be at least three elements present in an array whose summation equals the target to get a successful outcome else we end up returning False stating that there are no such triplets present in the array with this being the simple idea for Triplet Sum in Array.

Dry Run – Triplet Sum in Array

Suppose we have an array at hand with us and we need to fund the triplet sum in the array. We can do so by checking for each instance wherein on summing up the values of the triplet, if we get the sum equal to the target given, a triplet is fulfilling the criteria required.

We have the array at hand with target value. We start by placing the pointers at three successive starting positions, namely (i,j,k) and keep on checking if triplet sums equals target.

We increment the kth pointer at index 2 by to place it at 3 and check but the summation results in 2 with no success yet.

The k pointer is placed at the final index to check but the summation drops down to -2 making us keep checking further.

Now that the k pointer can be incremented, we place the j pointer one place ahead and rest the k position to be one index ahead of j and check the summation.

The k pointer moves to result in an unsuccessful summation of triplets.

K pointer moves to be at the (0,2,4) position.

Now, as we move the i pointer by one place and restore j and k values. We sum up the triplet to find that that result value equals the target. Thus, True will be returned.

Brute Force Approach – Algorithm, Code and Analysis

Now that we know the idea and the step by step process, we will be looking at the most intuitive approach to solve triplet sum in array. Here is an algorithm we can follow:

To find the three elements, we put two loops nested inside the outer loop to find all three elements on distinct indexes.

Three loops will be able to check for every possible triplet at distinct positions and append the valid triplet in the result list.

Algorithm

• Take array and target inputs
• Take three pointers in i,j,k.
• Set i as 0 and loop till n-3 i.e. First Loop.
  • Set j as i+1 and loop until n-1 i.e.Second Loop
    • Set k as j+1 and loop until n i.e.Third Loop
      • If a[i]+a[j]+a[k] == target and i!=j !=k then return True
• Return False

def find_triplet(nums, target_sum):
    for i in range(len(nums)-2):
        for j in range(i+1, len(nums)-1):
            for k in range(j+1, len(nums)):
                if nums[i] + nums[j] + nums[k] == target_sum:
                    print(f"Triplet is {nums[i]}, {nums[j]}, {nums[k]} at position {i},{j} and {k}")
                    return True
    return False

numbers = [-1,1,0,2,-2]
target = 3
print(find_triplet(numbers, target))

Output:

Triplet is 1, 0, 2 at position 1,2 and 3
True

Analysis of Algorithm

The approach offers a time complexity of O(N^3) which is pretty naive to be an optimal solution. The space complexity is constant i.e. O(1).

Hashmap Approach – Algorithm, Code and Analysis

Triplet Sum in Array problem can be solved with better time complexity using the hashmap approach where the outer loop points to an index and all the succeeding indexes are checked. Inside the outer loop, a dictionary holds the occurrence of an element then the third element is found.If the difference of target and element at i and j index is found in the map, we return True.

If no such occurrence is found, False is returned

Algorithm:

• Take array and target input
• Run a loop from i=0 till n-2.
  • Create an empty hash table using dictionary/set.
    • Run a loop from i+1 till n-1.
      • Return True if target – (a[i]+a[j]) exists in
        hash table else
      • Add a[j] into the hash table.
• Return False

def find_triplet(nums, target_sum):
    for i in range(len(nums)-2):
        s = {}
        cur = target_sum - nums[i]
        for j in range(i+1, len(nums)):
            if (cur - nums[j]) in s:
                print(f"Triplet is {nums[i]}, {nums[j]}, {cur-nums[j]} at {i},{j} and {s[cur-nums[j]]}")
                return True
            s[nums[j]] = j
    return False

numbers = [-1,1,0,2,-2]
target = 3
print(find_triplet(numbers, target))

Output:

Triplet is 1, 2, 0 at 1,3 and 2
True

Analysis of Code
Hashmap approach reduces the time complexity to O(N^2) in the worst case while the space complexity remains O(1).

Variation in Triplet Sum In Array

1. A variation of the question can be twisted where instead of just one triplet, the question asks you to return all triplets, in that case a result list or array can be maintained consisting of all the triplets appended and returned at the end.

2. Distinct triplet can be requested where in all three elements when summoned up must equal the target and must be three distinct or unique elements.

Conclusion – Triplet Sum In Array
Finding a triplet with a specific sum in an array is a common problem in programming. It involves searching for three elements in the array whose sum equals a given target value. This problem can be solved using various approaches, including brute force, sorting and two-pointers, or using a hash set. The choice of approach depends on the constraints of the problem and the desired efficiency.

Frequently Asked Questions (FAQs):

Q1: Why is finding a triplet sum in an array important?
Finding a triplet sum in an array is often useful for solving problems related to finding combinations or subsets that add up to a specific target value. It can be applied in various scenarios, such as finding three numbers that satisfy a certain condition or determining if there are three elements in an array that sum to zero.

Q2: How can I find a triplet sum in an array using a brute force approach?
The brute force approach involves checking all possible combinations of three elements in the array and comparing their sums to the target value. This can be done using nested loops, iterating through the array and checking all possible combinations. However, this approach has a time complexity of O(n^3), where n is the length of the array, making it inefficient for large arrays.

Q3: What is the sorting and two-pointer approach for finding a triplet sum?
The sorting and two-pointer approach involves sorting the array in ascending order and then using two-pointers to search for a triplet sum. By fixing one element and using two pointers to traverse the remaining elements, we can adjust the pointers based on the comparison with the target value. This approach has a time complexity of O(n^2), where n is the length of the array, as sorting the array takes O(n log n) time.

Q4: How does the hash set approach work for finding a triplet sum?
The hash set approach involves using a hash set to store the complement of the sum for each pair of elements encountered. By iterating through the array and checking if the complement of the current element exists in the hash set, we can find a triplet sum. This approach has a time complexity of O(n^2) as it requires two nested iterations through the array.

Q5: What should I consider when using the sorting and two-pointer approach or the hash set approach?
When using the sorting and two-pointer approach, the array needs to be sorted, which can modify the original order of the elements. If preserving the original order is important, the hash set approach might be a better choice. Additionally, the sorting and two-pointer approach may be more efficient for smaller arrays, while the hash set approach may handle larger arrays more effectively.

Q6: How do I handle cases where multiple triplet sums exist or when there are duplicate elements in the array?
Depending on the problem requirements, you may need to handle cases where multiple triplet sums exist or when duplicate elements are present in the array. This can involve returning all possible triplets, counting the number of unique triplets, or considering additional conditions to ensure uniqueness or specific combinations in the output.