Triplet Sum in Array

In this article, we will be looking at one of the most important problems in terms of programming concepts as well as coding-based interviews. We will start by explaining the problem statement and then breaking it down by discussing its dry run algorithm and look at the different approaches we can follow to implement the code.

For each of the problems discussed, we will be looking at its time and space complexity and how they fare among each other in terms of the best cost offered.

What is Triplet Sum in Array

As the title says triplet sum combined from triplet that can be three different elements and summation of those elements in an array. An input integer is given along with the array that must be matched to check if any triplet in an array sums up to be equal to the input integer.

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
In this article, we came across the problem Triplet Sum in Array and saw the breakdown of the problem and different methods to solve Triplet Sum in Array going through algorithm, code and analysis for each approach available at our helm.

Hope you found this article on Triplet Sum in Array helpful and we expect to see you again with an insightful piece of information.

FAQs Related to Triplet Sum in Array

1. What is the time complexity to find Triplet Sum in Array using the most optimal approach?
Ans. The most optimal solution has a time complexity of O(N^2)

2. What can be the variant of Triplet Sum in Array?
Ans. All triplets in the array can be a variant instead of finding the first occurring triplet.

3. What is the space complexity of Triplet Sum in Array?
Ans. The space complexity remains linear for Triplet Sum in Array.