How to find a triplet that sums to a given value in an array

Problem statement

Let's assume we have a fixed-size array with N elements. To find a triplet that sums to a given k value, we must find values at three unique indices that all add up to k.

For example, given the array [47, 6, 3, 8, 12, 10], a triplet that sums to k=28 is (6, 10, 12).

Simple solution

A simple solution to the problem is to generate all possible triplets, evaluate the sum of each, and return the triplet that sums to k. This would require a set of three nested loops, which would generate triplets and evaluate their sum.

This process is visualized below with an example:

However, this naive approach to the problem yields an inefficient solution that takes $O(N^3)$ time in the worst case.

Efficient solution

A more efficient solution to the problem requires us first to sort the array. Once we sort the array, we need a set of two nested loops.

The outer loop with the i counter goes to each element from the 0 index to N-3. The inner loop iterates over each element between i+1 and N-1, keeping track of the two positions, left_end and right_end. These are adjusted as the loop proceeds.

The illustration below demonstrates this process with an example:

This approach takes $O(N^2)$ time in the worst case, because there are just two loops, with one nested in the other. So, it is convenient to use a simple sorting technique like selection sort or bubble sort that also runs in $O(N^2)$ time, instead of a more efficient sorting technique like merge-sort or quick-sort that takes $O(Nlog(N))$ time. This is because the overall time complexity of this solution remains $O(N^2)$ .

Example

The lines highlighted in the code below implement the solution described above in Python and C++.

def findTripletSumToK(arr, N, k):
  arr.sort() # Sort the array in an ascending order
  for i in range(0, N-2): # Loop through all elements from index 0 to n-3
    left_end = i + 1 # Set initial left_end for each iteration of this outer loop    
    right_end = N-1 # Set initial right_end for each iteration of this outer loop
    while (1):
      if(left_end == right_end): # If left_end and right_end become the same, resume with the outer-loop
        break
      else:
        current_triplet = (arr[i] , arr[left_end] , arr[right_end]) # Make an empty tuple to fill with our triplet later
        if(sum(current_triplet) == k): # arr[i] + arr[left_end] + arr[right_end] == k
          return current_triplet
          
        elif (sum(current_triplet) > k): # arr[i] + arr[left_end] + arr[right_end] > k
          right_end = right_end - 1
        
        elif(sum(current_triplet) < k): # arr[i] + arr[left_end] + arr[right_end] < k 
          left_end = left_end + 1
  return ()
  
arr = [47, 6, 3, 8, 12, 10]
k = 28
N = len(arr)
  
ret = findTripletSumToK(arr, N, k)
print("Triplet is:" , ret)

Solution

Explanation

The findTripletSumToK() function implements the following steps:

We sort arr in ascending order.
Then, we iterate each element in an array from the 0 index to N-3.
During each iteration, we set left_end to i+1 and right_end to N-1, where i is the counter for the loop.
In a nested loop, we adjust left_end and right_end until they both become equal, such that:
- If the sum of the elements at i, left_end, and right_end is less than k, then we increment left_end.
- If the sum of the elements at i, left_end, and right_end is greater than k, then we decrement right_end.
- If the sum of the elements at i, left_end, and right_end is equal to k, then we return this triplet.
We return the triplet.

Free AI Mock Interviews

Coding Interview

Coding PatternsFree Interview

Gain insights and practical experience with coding patterns through targeted MCQs and coding problems, designed to match and challenge your expertise level.

System Design

You TubeFree Interview

Learn to design a video streaming platform like YouTube by tackling functional and non-functional requirements, core components, and high-level to detailed design challenges.

Free Resources