Triple Element Summation — Problem Statement & Solution Guide
Problem Description
Given a queue of integers and a target sum, find all unique triplets in the queue that sum up to the target value, with the constraint that each element can only be used once in each triplet.
Examples
Input
[1, 2, 3, 4, 5, 6, 7, 8, 9]
Output
[[1, 5, 9], [2, 4, 9], [2, 5, 8], [3, 4, 8], [3, 5, 7], [4, 5, 6]]
Explanation: Step-by-step: We first sort the input array. Then, we fix the first element and use two pointers to find the other two elements that sum up to the target value. We skip duplicates by checking if the current element is the same as the previous one. Finally, we add the triplet to the result list and move to the next element.
Input
[1, 1, 1]
Output
[[1, 1, 1]]
Explanation: Step-by-step: We first sort the input array. Then, we fix the first element and use two pointers to find the other two elements that sum up to the target value. Since all elements are the same, we can simply add the triplet to the result list.
Constraints
- The queue will contain at least three elements.
- The target sum is a positive integer.
Optimal Approach & Strategy
The optimized approach involves sorting the queue and using a two-pointer technique to find a pair of elements that, along with a fixed third element, sum up to the target value. This approach has a time complexity of O(n^2) and a space complexity of O(1).
Brute Force Approach
The brute force approach involves generating all possible triplets and checking if their sum equals the target value. However, this approach is inefficient and has a high time complexity. A more efficient solution would involve sorting and using a two-pointer technique.
Verified Code Solutions
function solution(nums, target) {
nums.sort((a, b) => a - b);
const result = [];
for (let i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] === nums[i - 1]) continue;
let left = i + 1;
let right = nums.length - 1;
while (left < right) {
const sum = nums[i] + nums[left] + nums[right];
if (sum === target) {
result.push([nums[i], nums[left], nums[right]]);
while (left < right && nums[left] === nums[left + 1]) left++;
while (left < right && nums[right] === nums[right - 1]) right--;
left++;
right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
return result;
}class Solution {
public:
vector<vector<int>> solution(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
vector<vector<int>> result;
for (int i = 0; i < nums.size() - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
int left = i + 1;
int right = nums.size() - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == target) {
result.push_back({nums[i], nums[left], nums[right]});
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
return result;
}
};class Solution {
public int solution(int[] nums, int target) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == target) {
result.add(Arrays.asList(nums[i], nums[left], nums[right]));
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
return result;
}
}def solution(nums, target):
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue
left = i + 1
right = len(nums) - 1
while left < right:
sum = nums[i] + nums[left] + nums[right]
if sum == target:
result.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
elif sum < target:
left += 1
else:
right -= 1
return resultfunction solution(nums, target) {
nums.sort((a, b) => a - b);
const result = [];
for (let i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] === nums[i - 1]) continue;
let left = i + 1;
let right = nums.length - 1;
while (left < right) {
const sum = nums[i] + nums[left] + nums[right];
if (sum === target) {
result.push([nums[i], nums[left], nums[right]]);
while (left < right && nums[left] === nums[left + 1]) left++;
while (left < right && nums[right] === nums[right - 1]) right--;
left++;
right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
return result;
}Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.