3 Sum
Medium
Given an array of integers called nums
, find triplets such that [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0
In simpler words, identify three elements in the given array sum such that the sum of these three elements equals to zero. The solution set must not contain duplicate triplets.
Approach
This problem can be solved using the 3 pointer approach. Three pointers namely i, j and k can be used for an optimal output. Among the 3 pointers, 1 will be fixed and 2 will be moving. In each iteration, we will check if the sum i.e. arr[i]+arr[j]+arr[k] is equal to the target i.e. 0.
- If the sum is greater, then we need lesser elements and so we will decrease the value of k (i.e. k–).
- If the sum is lesser than the target, we need a bigger value and so we will increase the value of j (i.e. j++).
- If the sum is equal to the target, we will simply insert the triplet i.e. arr[i], arr[j], arr[k], into our answer and move the pointers j and k skipping the duplicate elements.
Algorithm
- Sort the entire array to make the process of finding triplets easier.
- Use a loop with a fixed pointer
i
that iterates from 0 to n-1. - Inside the loop, check if the current element is the same as the previous one. If it is, skip to the next iteration to avoid duplicates.
- Use two moving pointers
j
(starting fromi + 1
) andk
(starting from the last index). - Move
j
forward andk
backward until they cross each other, while keepingi
fixed. - Check the sum
arr[i] + arr[j] + arr[k]
.- If the sum is greater than the target, decrease the value of
k
. - If the sum is lesser than the target, increase the value of
j
. - If the sum is equal to the target, add the triplet
(arr[i], arr[j], arr[k])
to the result list and skip duplicate elements while moving pointersj
andk
.
- If the sum is greater than the target, decrease the value of
- Continue until all unique triplets are found.
Complexity
- Time Complexity: O(NlogN)+O(N2), where N = size of the array.
- The pointer i, is running for approximately N times. And both the pointers j and k combined can run for approximately N times including the operation of skipping duplicates. So the total time complexity will be O(N2).
- Space Complexity: O(no. of quadruplets)
- This space is only used to store the answer. We are not using any extra space to solve this problem. So, from that perspective, space complexity can be written as O(1).
Code
## Java Code
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class ThreeSum {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
int n = nums.length;
Arrays.sort(nums); // Step 1: Sorting the array
for (int i = 0; i < n - 2; i++) { // Step 2: Loop with fixed pointer i
if (i > 0 && nums[i] == nums[i - 1]) // Avoid duplicates
continue;
int target = -nums[i]; // Target sum for the remaining two elements
int j = i + 1; // Two moving pointers
int k = n - 1;
while (j < k) { // Two-pointer technique
int sum = nums[j] + nums[k];
if (sum == target) { // If sum equals target
result.add(Arrays.asList(nums[i], nums[j], nums[k]));
j++;
k--;
while (j < k && nums[j] == nums[j - 1]) j++; // Skip duplicates
while (j < k && nums[k] == nums[k + 1]) k--; // Skip duplicates
} else if (sum < target) { // If sum is lesser than target
j++;
} else { // If sum is greater than target
k--;
}
}
}
return result;
}
public static void main(String[] args) {
ThreeSum solution = new ThreeSum();
int[] nums = {-1, 0, 1, 2, -1, -4};
List<List<Integer>> result = solution.threeSum(nums);
System.out.println("Unique triplets that sum up to 0:");
for (List<Integer> triplet : result) {
System.out.println(triplet);
}
}
}
Output
Unique triplets that sum up to 0:
[-1, -1, 2]
[-1, 0, 1]
Thanks for feedback.