ArrayProblem 28 of 36
Find the triplet that sum to a given value
Problem Statement
Given an array of integers and a target sum, find if there exists a triplet in the array whose sum equals the target. Return the triplet if found.
Example:
- Input:
arr = [1, 4, 45, 6, 10, 8],target = 22 - Output:
[4, 10, 8] - Explanation: 4 + 10 + 8 = 22
Approach 1: Brute Force (Three Nested Loops)
Intuition
Try all possible triplets and check if their sum equals the target.
Algorithm
- Use three nested loops to generate all triplets
- For each triplet, check if sum equals target
- Return the triplet if found
java
import java.util.*;
public class Solution {
public int[] findTriplet(int[] arr, int target) {
int n = arr.length;
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
for (int k = j + 1; k < n; k++) {
if (arr[i] + arr[j] + arr[k] == target) {
return new int[]{arr[i], arr[j], arr[k]};
}
}
}
}
return new int[]{}; // No triplet found
}
public boolean hasTripletWithSum(int[] arr, int target) {
int n = arr.length;
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
for (int k = j + 1; k < n; k++) {
if (arr[i] + arr[j] + arr[k] == target) {
return true;
}
}
}
}
return false;
}
}Complexity Analysis
- Time Complexity: O(n³) - Three nested loops
- Space Complexity: O(1) - No extra space used
Approach 2: Hashing (Two Loops + HashSet)
Intuition
Fix one element, then use a hash set to find if a pair exists that completes the triplet.
Algorithm
- For each element arr[i], we need to find pair with sum = target - arr[i]
- Use a hash set to find the pair in O(n)
- Total: O(n²)
java
import java.util.*;
public class Solution {
public int[] findTriplet(int[] arr, int target) {
int n = arr.length;
for (int i = 0; i < n - 2; i++) {
int pairSum = target - arr[i];
Set<Integer> seen = new HashSet<>();
for (int j = i + 1; j < n; j++) {
int complement = pairSum - arr[j];
if (seen.contains(complement)) {
return new int[]{arr[i], complement, arr[j]};
}
seen.add(arr[j]);
}
}
return new int[]{};
}
public boolean hasTripletWithSum(int[] arr, int target) {
int n = arr.length;
for (int i = 0; i < n - 2; i++) {
int pairSum = target - arr[i];
Set<Integer> seen = new HashSet<>();
for (int j = i + 1; j < n; j++) {
int complement = pairSum - arr[j];
if (seen.contains(complement)) {
return true;
}
seen.add(arr[j]);
}
}
return false;
}
}Complexity Analysis
- Time Complexity: O(n²) - Outer loop O(n), inner loop with hash operations O(n)
- Space Complexity: O(n) - Hash set can store up to n elements
Approach 3: Optimal - Sorting with Two Pointers
Intuition
Sort the array. Fix one element, then use two pointers technique to find the remaining pair.
Algorithm
- Sort the array
- For each element arr[i], use two pointers (left, right) in the remaining subarray
- If sum < target, move left pointer right
- If sum > target, move right pointer left
- If sum == target, found the triplet
java
import java.util.*;
public class Solution {
public int[] findTriplet(int[] arr, int target) {
int n = arr.length;
Arrays.sort(arr);
for (int i = 0; i < n - 2; i++) {
int left = i + 1;
int right = n - 1;
int pairSum = target - arr[i];
while (left < right) {
int currentSum = arr[left] + arr[right];
if (currentSum == pairSum) {
return new int[]{arr[i], arr[left], arr[right]};
} else if (currentSum < pairSum) {
left++;
} else {
right--;
}
}
}
return new int[]{};
}
// Find all unique triplets
public List<List<Integer>> findAllTriplets(int[] arr, int target) {
int n = arr.length;
Arrays.sort(arr);
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < n - 2; i++) {
// Skip duplicates for first element
if (i > 0 && arr[i] == arr[i - 1]) continue;
int left = i + 1;
int right = n - 1;
int pairSum = target - arr[i];
while (left < right) {
int currentSum = arr[left] + arr[right];
if (currentSum == pairSum) {
result.add(Arrays.asList(arr[i], arr[left], arr[right]));
// Skip duplicates
while (left < right && arr[left] == arr[left + 1]) left++;
while (left < right && arr[right] == arr[right - 1]) right--;
left++;
right--;
} else if (currentSum < pairSum) {
left++;
} else {
right--;
}
}
}
return result;
}
}Complexity Analysis
- Time Complexity: O(n²) - Sorting O(n log n) + O(n²) for two pointer search
- Space Complexity: O(1) - Only pointers used (excluding sorting space)
Key Takeaways
- Reduce to 2Sum - Fix one element and solve 2Sum for the remaining
- Two pointers on sorted array - Enables O(n) pair finding instead of O(n²)
- Handle duplicates - Skip duplicate elements to find unique triplets
- Related problems - 3Sum closest, 4Sum, kSum all follow similar patterns