Python – Find a Triplet in an Array That Sums to a Given Value

This problem involves finding three numbers (a triplet) in an array whose sum equals a given target value. It is a popular question in data structures and algorithms interviews.

In this tutorial, we will explain the problem, provide sample inputs and outputs, outline the solution steps, and present a Python program to solve it.

Problem Statement

Given an array arr of integers and a target sum S, your task is to find any triplet within the array such that the sum of its three elements equals S. If such a triplet exists, return it; otherwise, indicate that no valid triplet was found.

Sample Input and Output

Example 1:

</>
Copy
Input: arr = [12, 3, 4, 1, 6, 9], S = 24
Output: [3, 9, 12]

Example 2:

</>
Copy
Input: arr = [1, 2, 3, 4, 5, 6], S = 12
Output: [1, 5, 6]  # One possible triplet

Solution Approach

We can solve this problem using the two-pointer technique after sorting the array. The main steps are:

  1. Sort the Array: Sorting the array allows us to efficiently use two pointers to find pairs that sum to a desired value.
  2. Fix One Element: Iterate through the array and fix one element of the potential triplet.
  3. Find the Remaining Pair: For the current fixed element, use two pointers (one starting just after the fixed element and one at the end of the array) to search for two numbers whose sum equals S - fixed_element.
  4. Check and Update Pointers: If the sum of the triplet matches S, return the triplet. If the sum is less than S, move the left pointer to the right; if it’s greater, move the right pointer to the left.
  5. Repeat: Continue the process until a valid triplet is found or all possibilities are exhausted.

Python Program

</>
Copy
def find_triplet(arr, S):
    # Sort the array to use the two-pointer approach
    arr.sort()
    n = len(arr)
    
    # Iterate through the array
    for i in range(n - 2):
        left = i + 1
        right = n - 1
        
        # Use two pointers to find a pair such that arr[i] + arr[left] + arr[right] == S
        while left < right:
            current_sum = arr[i] + arr[left] + arr[right]
            if current_sum == S:
                return [arr[i], arr[left], arr[right]]
            elif current_sum < S:
                left += 1
            else:
                right -= 1
    return None

# Example 1
arr1 = [12, 3, 4, 1, 6, 9]
S1 = 24
result1 = find_triplet(arr1, S1)
print("Triplet for Example 1:", result1)

# Example 2
arr2 = [1, 2, 3, 4, 5, 6]
S2 = 12
result2 = find_triplet(arr2, S2)
print("Triplet for Example 2:", result2)

Output:

Triplet for Example 1: [3, 9, 12]
Triplet for Example 2: [1, 5, 6]

Note: The triplet returned might vary if there are multiple valid solutions. The approach shown returns the first valid triplet found.

Conclusion

This tutorial demonstrated how to find a triplet in an array that sums to a given target using the two-pointer technique. By sorting the array and iteratively searching for pairs that, along with a fixed element, add up to the target, we can efficiently solve the problem with a time complexity of O(n2).