876765. Find all distinct triplets with given sum
Here is a detailed Markdown blog post for the GeeksforGeeks problem:
Find all distinct triplets with given sum
Summary
Given an array of integers, find all distinct triplets that add up to a given sum. This problem involves sorting and using two pointers to efficiently solve this problem.
Detailed Explanation
To solve this problem, we can sort the array first. Then, for each triplet, we fix one element and use two pointers to find the other two elements that add up to the remaining sum. The key concept here is the two-pointer algorithm, which helps us avoid duplicate triplets by ensuring that the next pair of numbers found will be less than or equal to the current one.
Here's a step-by-step breakdown of the solution:
- Sort the array in ascending order.
- Fix an element at index
i. - Initialize two pointers,
leftandright, to the first element (arr[0]) and the last element (arr[n-1]) respectively. - Calculate the sum of the fixed element and the elements at
leftandright. If this sum is equal to the target sum, add the triplet (arr[i], arr[left], arr[right]) to our result list. - Move the pointers based on the calculated sum:
- If the sum is less than the target sum, move the
rightpointer towards the beginning of the array to increase the sum. - If the sum is greater than the target sum, move the
leftpointer towards the end of the array to decrease the sum.
- If the sum is less than the target sum, move the
- Repeat steps 2-5 until
ireaches the end of the array.
Time complexity: O(n^2) where n is the length of the input array. The two-pointer algorithm runs in linear time for each fixed element, and we have to fix all elements in the array. Space complexity: O(1). We only use a constant amount of space to store our result list and the pointers.
Optimized Solutions
Java
public class FindDistinctTriplets {
public static List<List<Integer>> findTriplets(int[] arr, int targetSum) {
Arrays.sort(arr);
List<List<Integer>> triplets = new ArrayList<>();
for (int i = 0; i < arr.length - 2; i++) {
if (i > 0 && arr[i] == arr[i-1]) continue;
int left = i + 1, right = arr.length - 1;
while (left < right) {
int sum = arr[i] + arr[left] + arr[right];
if (sum == targetSum) {
triplets.add(Arrays.asList(arr[i], arr[left], arr[right]));
left++;
right--;
while (left < right && arr[left] == arr[left-1]) left++;
while (left < right && arr[right] == arr[right+1]) right--;
} else if (sum < targetSum) {
left++;
} else {
right--;
}
}
}
return triplets;
}
}