875869. Find all triplets with given sum
Find all triplets with given sum
Slug: print-all-triplets-with-given-sum Difficulty: Medium Id: 875869 Topic Tags: Sorting, two-pointer-algorithm, Arrays Company Tags: None
Summary
Given an array and a target sum, find all unique triplets in the array that add up to the given sum. This problem requires sorting the array and then using two pointers to find the triplets.
Detailed Explanation
To solve this problem, we will sort the input array first, which allows us to efficiently use a two-pointer approach to find the triplets. The basic idea is to fix one element and then use the other two elements to form a pair that adds up to the target sum.
Here's a step-by-step breakdown of the solution:
- Sort the input array in ascending order.
- Iterate over each element in the sorted array. For each element, consider it as the first element of a triplet.
- Fix the first element and use two pointers, one starting from the next element and the other from the end of the array, to find a pair that adds up to the target sum minus the fixed element.
- If the sum of the two elements is less than the target sum, move the left pointer to the right.
- If the sum is greater than the target sum, move the right pointer to the left.
- When the sum equals the target sum, print the triplet and update the pointers accordingly.
Here's an ASCII art diagram to illustrate the two-pointer approach:
+-----+ +-----+
| A | | B |
+-----+ +-----+
| |
| fixed point |
v v
+-----+ +-----+
| C | | D |
+-----+ +-----+
Time complexity: O(n^2), where n is the length of the input array. This is because we have a nested loop structure. Space complexity: O(1), as we only use a constant amount of space to store the pointers and temporary variables.
Optimized Solutions
Java
import java.util.Arrays;
public class Triplets {
public static void findTriplets(int[] arr, int targetSum) {
Arrays.sort(arr);
for (int i = 0; i < arr.length - 2; i++) {
int left = i + 1;
int right = arr.length - 1;
while (left < right) {
int sum = arr[i] + arr[left] + arr[right];
if (sum == targetSum) {
System.out.println(Arrays.toString(new int[]{arr[i], arr[left], arr[right]}));
left++;
right--;
} else if (sum < targetSum) {
left++;
} else {
right--;
}
}
}
}
}