Three Sum
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.
Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.
Example 2:
Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.
Example 3:
Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.
Constraints:
- 3 <= nums.length <= 3000
- -105 <= nums[i] <= 105
Step 1 : – Template Implementation
There are two types of two pointer templates.
1). Opposite direction two pointer template
2). Same direction two pointer template
Based on our analysis of the Three Sum problem statement, we need to extend the opposite direction pointers template from two pointers to three pointers. To achieve this, we introduce an additional for loop to handle the extra index. Inside this loop, we set the i pointer at the first index of the array and move the left pointer one step ahead in the array to begin the three-pointer process and as per the approach sort the array so will use Arrays sort() method.
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
int left = i+1;
int right = nums.length - 1;
while (left < right) {
//code
if (param1 == param2) {
// code
left++;
right--;
} else if (param1 < param2) {
left++;
} else {
right--;
}
}
}
return result;
}
}Step 2 : – I/O parameters.
Input parameters :- To calculate the value of param1, we add the values of the elements at the i,left and right indices. This sum becomes our triplet and replaced param2 with the target value as 0.
Output parameter :- We need to return the triplet formed by the elements at indices i, left, and right when their combined sum equals zero.Prepare the return parameter
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
int left = i+1;
int right = nums.length - 1;
while (left < right) {
int triplet = nums[i] + nums[left] + nums[right];
if (triplet == 0) {
result.add(Arrays.asList(nums[i], nums[left], nums[right]));
left++;
right--;
} else if (triplet < 0) {
left++;
} else {
right--;
}
}
}
return result;
}
}
Step 3 : – Skip the duplicates.
We need to skip duplicates for the i index in the three-pointer approach to ensure unique triplets in the result.
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
// Skip duplicate `i` values
if (i > 0 && nums[i] == nums[i - 1]) continue;
int left = i+1;
int right = nums.length - 1;
while (left < right) {
int triplet = nums[i] + nums[left] + nums[right];
if (triplet == 0) {
result.add(Arrays.asList(nums[i], nums[left], nums[right]));
left++;
right--;
} else if (triplet < 0) {
left++;
} else {
right--;
}
}
}
return result;
}
}
Step 4 – Handle duplicate values for the left and right pointers
The corner test case [-2,0,3,-1,4,0,3,4,1,1,1,-3,-5,4,0] fails because it produces duplicate triplets in the result.
To resolve this, we need to skip over duplicate values for both the left and right pointers after finding a valid triplet.
This ensures that each unique triplet is included only once in the final result.
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
// Skip duplicate `i` values
if (i > 0 && nums[i] == nums[i - 1]) continue;
int left = i+1;
int right = nums.length - 1;
while (left < right) {
int triplet = nums[i] + nums[left] + nums[right];
if (triplet == 0) {
result.add(Arrays.asList(nums[i], nums[left], nums[right]));
// Skip duplicates
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
} else if (triplet < 0) {
left++;
} else {
right--;
}
}
}
return result;
}
}
Final Code : –
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
// Skip duplicate `i` values
if (i > 0 && nums[i] == nums[i - 1]) continue;
int left = i+1;
int right = nums.length - 1;
while (left < right) {
int triplet = nums[i] + nums[left] + nums[right];
if (triplet == 0) {
result.add(Arrays.asList(nums[i], nums[left], nums[right]));
// Skip duplicates
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
} else if (triplet < 0) {
left++;
} else {
right--;
}
}
}
return result;
}
}