Find triplets with zero sum (3Sum Problem). Given an array of integers, write a code to find all unique triplets in the array which gives the sum of zero.
Note: The solution set must not contain duplicate triplets.
For example –
Example 1:
Input: {-1, 0, 1, 2, -1, -4}
Output: {-1, 0, 1}, {-1, -1, 2}
Example 2:
Input: {-8, -7, 5, 2}
Output: {-7, 5, 2}
3Sum Problem
This problem is very important in terms of interviews. It is already asked in Amazon, Facebook, Adobe and many other good companies.
In this tutorial, I am going to discuss multiple approaches and their time complexities to solve this problem efficiently.
Method 1: Brute Force Approach
The simplest way to solve 3sum problem is by using a brute force approach. In this approach, we use three for loops to find all unique triplets in the array which gives the sum of zero.
The time complexity of this approach is O(n^3).
Find a peak element in an array
Method 2: Use Sorting
The better way to solve this problem is to first sort the array. Then run two loops to find triplets that sum to zero.
I have also explained this approach using a video tutorial, The link of that video tutorial is mentioned at the end of this post.
The time complexity of this approach is O(n^2).
Find the element that appears once in a sorted array
Find Triplets with Zero Sum (3Sum Problem) – Java Code
Let’s implement the second approach to solve 3 sum problem using java code.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
//3Sum Problem Java Code public class TripletWithZeroSum { public static List<List<Integer>> threeSum(int[] arr) { //Declare a list to hold multiple triplets List<List<Integer>> result = new ArrayList<>(); //Sort an array Arrays.sort(arr); //Run a loop from 0 to n for (int i = 0; i < arr.length; i++) { //Declare and intialize two indexes int start = i + 1; int end = arr.length - 1; /* To ignore duplicates, Never consider consecutive indices with same value. */ if (i > 0 && arr[i] == arr[i - 1]) { continue; } while (start < end) { //Ignore duplicates if (end < arr.length - 1 && arr[end] == arr[end + 1]) { end--; continue; } //If triplets is found then put them in a list if (arr[i] + arr[start] + arr[end] == 0) { List<Integer> val = Arrays.asList(arr[i],arr[start],arr[end]); result.add(val); start++; end--; } else if (arr[i] + arr[start] + arr[end] < 0) { start++; } else { end--; } } } return result; } public static void main(String[] args) { int[] arr = {-1, 0, 1, 2, -1, -4}; List<List<Integer>> result = threeSum(arr); result.forEach(values -> { System.out.println(values); }); } } |
In this approach, to ignore duplicates we have explicitly checked consecutive indices with same value. We can also use HashSet to ignore duplicate values.
Find triplet with given sum in an array
3Sum LeetCode Solution – Java Code
Let’s write a code to find all unique triplets with zero sum using HashSet. We are using HashSet to solve this problem because it does not allow duplicates and it’s lookup time is O(1).
Sorting algorithms and their time complexities
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
//3Sum Java Code public List<List<Integer>> threeSum(int[] nums) { //If array size is less than 3 if(nums.length < 3) { return new ArrayList<>(); } Set<ArrayList<Integer>> result = new HashSet<>(); //Sort array Arrays.sort(nums); for(int i = 0; i < nums.length; i++) { int start = i+1; int end = nums.length-1; while(start < end) { if(nums[i] + nums[start] + nums[end] == 0) { ArrayList<Integer> output = new ArrayList<>(); output.add(nums[i]); output.add(nums[start]); output.add(nums[end]); result.add(output); start++; end--; } else if (nums[i] + nums[start] + nums[end] > 0) { end--; } else { start++; } } } return new ArrayList<>(result); } |
3 Sum Zero InterviewBit Solution – Java Code
We use the similar approach which i have already discussed. First we sort the array and then we run two for loops to find three elements whose sum is equal to zero.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
//3 Sum Zero InterviewBit Solution public class Solution { public ArrayList<ArrayList<Integer>> threeSum(ArrayList<Integer> A) { if(A.size() < 3) { return new ArrayList<>(); } Set<ArrayList<Integer>> result = new HashSet<>(); Collections.sort(A); for(int i = 0; i < A.size(); i++) { int start = i+1; int end = A.size()-1; while(start < end) { if(A.get(i) + A.get(start) + A.get(end) == 0) { ArrayList<Integer> output = new ArrayList<>(); output.add(A.get(i)); output.add(A.get(start)); output.add(A.get(end)); result.add(output); start++; end--; } else if (A.get(i) + A.get(start) + A.get(end) > 0) { end--; } else { start++; } } } return new ArrayList<>(result); } } |
3Sum Solution Java Video Tutorial
In this tutorial, I have explained multiple approaches and it’s time complexities to solve this problem. If you know any other approach to solve this problem efficiently then let us know through your comments.
