876773. All triplets with given sum
Find All Triplets with Given Sum
Summary
Given an array of integers, find all triplets in the array that sum up to a given value. This problem requires sorting the array and then using three pointers technique to find all triplets.
Detailed Explanation
To solve this problem, we can start by sorting the input array in ascending order. Then, for each element in the array, we can use two pointers (one starting from the current element and one from the end of the array) to find a pair that sums up to the given value. If such a pair is found, we add it to our result list.
Here's a step-by-step breakdown:
- Sort the input array in ascending order.
- Iterate through the sorted array, considering each element as the first element of a potential triplet.
- Initialize two pointers,
leftandright, both pointing to elements in the array that are to the right and left of the current element, respectively. - Calculate the sum of the three elements (
current element + left element + right element). If this sum is equal to the given value, add the triplet to our result list. - If the sum is less than the given value, increment
leftto increase the sum. If the sum is greater than the given value, decrementrightto decrease the sum. - Repeat steps 3-5 until all triplets have been considered.
Here's a simple diagram of the three pointers technique:
+---------------+
| current |
+---------------+
|
| left
v
+---------------+
| element 1 |
+---------------+
|
| right
v
+---------------+
| element n-2|
+---------------+
Time complexity: O(n^2), where n is the length of the input array. This is because for each element, we are potentially scanning the entire array to find the correct pair.
Space complexity: O(1), since we only use a constant amount of space to store our result list and pointers.
Optimized Solutions
Here are optimized solutions in various programming languages:
Java
import java.util.ArrayList;
import java.util.Arrays;
public class Main {
public static void findTriplets(int[] arr, int sum) {
Arrays.sort(arr);
ArrayList<int[]> 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 currentSum = arr[i] + arr[left] + arr[right];
if (currentSum < sum) {
left++;
} else if (currentSum > sum) {
right--;
} else {
triplets.add(new int[]{arr[i], arr[left], arr[right]});
while (left < right && arr[left] == arr[left+1]) left++;
while (left < right && arr[right] == arr[right-1]) right--;
left++; right--;
}
}
}
// Print the triplets
for (int[] triplet : triplets) {
System.out.println(Arrays.toString(triplet));
}
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6};
findTriplets(arr, 9);
}
}