In this tutorial, I will demonstrate how to solve the 3Sum problem in Java. This is a popular array-based coding interview question that helps you understand sorting, two-pointer techniques, duplicate handling, and efficient searching.
The 3Sum problem asks you to find all unique combinations of three numbers in an array whose sum equals zero. Each triplet must contain elements from three different indexes.
For example, consider the array [-1, 0, 1, 2, -1, -4]. The unique triplets whose sum is zero are [-1, -1, 2] and [-1, 0, 1].
A straightforward solution uses three nested loops to examine every possible triplet. However, that approach has cubic time complexity. A more efficient approach sorts the array and uses two pointers to find matching pairs.
In this tutorial, you will learn how to solve the 3Sum problem using sorting and two pointers, how to avoid duplicate triplets, and how to implement a brute-force solution. I will also explain the algorithm with a dry run, complexity analysis, and important edge cases.
1. Problem Statement
Given an integer array, find all unique triplets whose sum equals zero.
Each triplet must satisfy the following conditions:
- It contains exactly three elements.
- The elements come from three different array indexes.
- The sum of the three elements is zero.
- Duplicate triplets are not included in the result.
The order of triplets in the result is not important unless a specific problem statement requires otherwise.
Example 1
Input: nums = [-1, 0, 1, 2, -1, -4] Output: [[-1, -1, 2], [-1, 0, 1]]
Explanation:
-1 + -1 + 2 = 0 -1 + 0 + 1 = 0
These are the only unique triplets that satisfy the condition.
Example 2
Input: nums = [0, 1, 1] Output: []
No combination of three distinct indexes produces a sum of zero.
Example 3
Input: nums = [0, 0, 0, 0] Output: [[0, 0, 0]]
Although four zeros are available, the triplet [0, 0, 0] should appear only once.
2. Understanding the 3Sum Problem
The 3Sum problem is closely related to the Two Sum problem.
In Two Sum, you find two numbers whose sum equals a target.
In 3Sum, you select one number and then search for two other numbers whose sum is the negative of the selected number.
Mathematically:
a + b + c = 0 Therefore: b + c = -a
Once the array is sorted, the two-pointer technique can efficiently find the remaining pair.
The main challenge is avoiding duplicate triplets when the array contains repeated values.
3. Method 1: Solve 3Sum Using Sorting and Two Pointers
The sorting and two-pointer approach is the recommended solution for the 3Sum problem.
The algorithm first sorts the array in ascending order.
It then selects each element as the first number of a potential triplet and uses two pointers to find the remaining two numbers.
How the Algorithm Works
- Sort the array in ascending order.
- Iterate through the array, selecting one number at a time.
- Skip repeated values of the selected number to avoid duplicate triplets.
- Initialize the left pointer immediately after the selected number.
- Initialize the right pointer at the last index.
- Calculate the sum of the three selected numbers.
- If the sum is zero, add the triplet to the result.
- If the sum is negative, move the left pointer forward.
- If the sum is positive, move the right pointer backward.
- After finding a triplet, skip duplicate values before continuing.
Java Program Using Sorting and Two Pointers
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class ThreeSum {
/**
* Finds all unique triplets whose sum is zero.
*
* @param nums input integer array
* @return list of unique triplets
*/
public static List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
if (nums == null || nums.length < 3) {
return result;
}
// Copy to avoid modifying the original array
int[] sorted = Arrays.copyOf(nums, nums.length);
Arrays.sort(sorted);
for (int i = 0; i < sorted.length - 2; i++) {
// Skip duplicate first elements
if (i > 0 && sorted[i] == sorted[i - 1]) {
continue;
}
// No future triplet can sum to zero
if (sorted[i] > 0) {
break;
}
int left = i + 1;
int right = sorted.length - 1;
while (left < right) {
// Use long to avoid integer overflow
long sum = (long) sorted[i]
+ sorted[left]
+ sorted[right];
if (sum == 0) {
result.add(Arrays.asList(
sorted[i],
sorted[left],
sorted[right]
));
left++;
right--;
// Skip duplicate left values
while (left < right
&& sorted[left] == sorted[left - 1]) {
left++;
}
// Skip duplicate right values
while (left < right
&& sorted[right] == sorted[right + 1]) {
right--;
}
} else if (sum < 0) {
// Need a larger sum
left++;
} else {
// Need a smaller sum
right--;
}
}
}
return result;
}
public static void main(String[] args) {
int[] nums = {-1, 0, 1, 2, -1, -4};
List<List<Integer>> result = threeSum(nums);
System.out.println("Input Array: "
+ Arrays.toString(nums));
System.out.println("Unique Triplets: " + result);
}
}Output
Input Array: [-1, 0, 1, 2, -1, -4] Unique Triplets: [[-1, -1, 2], [-1, 0, 1]]
The program finds both unique triplets in quadratic time without modifying the original input array.
4. Step-by-Step Explanation of the Two-Pointer Solution
Step 1: Create the Result List
List<List<Integer>> result = new ArrayList<>();Each valid triplet is represented as a List of three integers.
The outer List stores all unique triplets.
Step 2: Validate the Input
if (nums == null || nums.length < 3) {
return result;
}At least three array elements are required to form a triplet.
If the input is null or contains fewer than three elements, the method returns an empty List.
Step 3: Sort the Array
int[] sorted = Arrays.copyOf(nums, nums.length);
Arrays.sort(sorted);The program copies the input array before sorting so the original array remains unchanged.
For example:
Original: [-1, 0, 1, 2, -1, -4] Sorted: [-4, -1, -1, 0, 1, 2]
Sorting makes it possible to adjust the sum efficiently by moving the left or right pointer.
Step 4: Select the First Element
for (int i = 0; i < sorted.length - 2; i++) {The outer loop selects each element as the first number of a possible triplet.
The loop stops before the last two positions because at least two elements must remain.
Step 5: Skip Duplicate First Elements
if (i > 0 && sorted[i] == sorted[i - 1]) {
continue;
}If the current element equals the previous element, the program skips it.
Otherwise, the same set of triplets could be generated more than once.
Step 6: Stop When the First Element Is Positive
if (sorted[i] > 0) {
break;
}Because the array is sorted, all elements after a positive first element are also positive.
Three positive numbers cannot have a sum of zero.
Therefore, the loop can stop early.
Step 7: Initialize Two Pointers
int left = i + 1;
int right = sorted.length - 1;The left pointer starts immediately after the selected first element.
The right pointer starts at the end of the sorted array.
Step 8: Calculate the Sum
long sum = (long) sorted[i]
+ sorted[left]
+ sorted[right];The program adds the three selected numbers.
Using long prevents incorrect results caused by overflowing the int range when adding large integer values.
Step 9: Handle a Valid Triplet
if (sum == 0) {
result.add(Arrays.asList(
sorted[i],
sorted[left],
sorted[right]
));
left++;
right--;
}When the sum equals zero, the program adds the triplet to the result.
It then moves both pointers because the current pair has already been processed.
Step 10: Skip Duplicate Values
while (left < right
&& sorted[left] == sorted[left - 1]) {
left++;
}
while (left < right
&& sorted[right] == sorted[right + 1]) {
right--;
}After finding a valid triplet, the algorithm skips repeated values at both pointer positions.
This prevents duplicate triplets from being added to the result.
Step 11: Adjust the Pointers
If the sum is less than zero, the algorithm needs a larger value:
left++;Moving the left pointer forward selects a value that is greater than or equal to the previous value.
If the sum is greater than zero, the algorithm needs a smaller value:
right--;Moving the right pointer backward selects a value that is less than or equal to the previous value.
5. Dry Run: Finding Unique Triplets Whose Sum Is Zero
Let's understand the algorithm using this input:
Input: [-1, 0, 1, 2, -1, -4] After Sorting: [-4, -1, -1, 0, 1, 2]
The algorithm selects a first element and searches for a matching pair using two pointers.
| First | Left | Right | Sum | Action |
|---|---|---|---|---|
| -4 | -1 | 2 | -3 | Move left |
| -4 | -1 | 2 | -3 | Move left |
| -4 | 0 | 2 | -2 | Move left |
| -4 | 1 | 2 | -1 | Move left |
| -1 | -1 | 2 | 0 | Add [-1, -1, 2] |
| -1 | 0 | 1 | 0 | Add [-1, 0, 1] |
After processing the first value -4, no matching pair is found.
The next unique first value is -1.
The algorithm finds two valid combinations:
-1 + -1 + 2 = 0 -1 + 0 + 1 = 0
The next -1 is skipped because it would generate duplicate triplets.
Final result:
[[-1, -1, 2], [-1, 0, 1]]
6. Method 2: Solve 3Sum Using Brute Force
The brute-force approach uses three nested loops to examine every possible combination of three different indexes.
When a combination sums to zero, the program sorts that triplet and stores it in a Set.
A Set helps eliminate duplicate triplets.
Java Program Using Brute Force and HashSet
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class ThreeSumBruteForce {
public static List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
if (nums == null || nums.length < 3) {
return result;
}
Set<List<Integer>> uniqueTriplets =
new HashSet<>();
for (int i = 0; i < nums.length - 2; i++) {
for (int j = i + 1; j < nums.length - 1; j++) {
for (int k = j + 1; k < nums.length; k++) {
long sum = (long) nums[i]
+ nums[j]
+ nums[k];
if (sum == 0) {
int[] triplet = {
nums[i],
nums[j],
nums[k]
};
Arrays.sort(triplet);
uniqueTriplets.add(Arrays.asList(
triplet[0],
triplet[1],
triplet[2]
));
}
}
}
}
result.addAll(uniqueTriplets);
return result;
}
public static void main(String[] args) {
int[] nums = {-1, 0, 1, 2, -1, -4};
List<List<Integer>> result = threeSum(nums);
System.out.println("Unique Triplets:");
for (List<Integer> triplet : result) {
System.out.println(triplet);
}
}
}Possible Output
Unique Triplets: [-1, -1, 2] [-1, 0, 1]
Note: HashSet does not guarantee iteration order, so the two triplets may be printed in a different order.
How the Brute-Force Approach Works
- Select the first element using the outer loop.
- Select the second element using the middle loop.
- Select the third element using the inner loop.
- Calculate the sum of all three values.
- If the sum is zero, sort the three values.
- Add the sorted triplet to a Set to prevent duplicates.
- Return the unique triplets.
This method is easy to understand, but its three nested loops make it inefficient for large arrays.
7. Time and Space Complexity
Let's compare the approaches.
| Approach | Time Complexity | Additional Space | Recommendation |
|---|---|---|---|
| Sorting + Two Pointers | O(n²) | O(n) for the copied array, excluding results | Recommended |
| Brute Force + HashSet | O(n³) expected | O(r) for unique triplets | Beginner alternative |
Here, n represents the number of array elements and r represents the number of unique triplets stored.
Why Is the Two-Pointer Approach O(n²)?
Sorting requires up to O(n log n) time.
The outer loop selects a first element, and the two pointers scan the remaining portion of the array.
For each first element, the two-pointer scan takes at most O(n) time.
Therefore, the total time complexity is:
O(n log n) + O(n²) = O(n²)
Why Is Brute Force O(n³)?
The brute-force approach examines combinations of three indexes.
There are up to:
n × (n - 1) × (n - 2) / 6
such combinations.
Therefore, its time complexity is O(n³).
Space Complexity
The recommended program creates a copy of the input array before sorting, requiring O(n) additional storage.
If modifying the original array is permitted, you can sort it directly and avoid that copy. The two-pointer search itself uses constant auxiliary space.
The returned triplets also occupy memory. In the worst case, the number of distinct triplets can grow quadratically with the input size.
8. Handling Important Edge Cases
Case 1: Empty Array
Input: [] Output: []
An empty array cannot contain a triplet.
Case 2: Fewer Than Three Elements
Input: [-1, 1] Output: []
At least three different indexes are required.
Case 3: All Elements Are Zero
Input: [0, 0, 0, 0] Output: [[0, 0, 0]]
The algorithm returns only one unique triplet, even though several index combinations contain three zeros.
Case 4: No Valid Triplet
Input: [1, 2, 3, 4] Output: []
All values are positive, so no three elements can sum to zero.
Case 5: Negative and Positive Numbers
Input: [-2, 0, 1, 1, 2] Output: [[-2, 0, 2], [-2, 1, 1]]
The algorithm correctly identifies both unique triplets.
Case 6: Duplicate Values
Input: [-1, -1, -1, 2, 2] Output: [[-1, -1, 2]]
The repeated values can form several index combinations, but only one unique triplet is returned.
Case 7: Integer Overflow
Adding three large int values can overflow Java's 32-bit integer range.
To avoid incorrect results, the program converts the first value to long before performing the addition.
long sum = (long) sorted[i]
+ sorted[left]
+ sorted[right];This ensures the sum is calculated using 64-bit arithmetic.
9. Common Mistakes to Avoid
Mistake 1: Forgetting to Sort the Array
The two-pointer technique relies on the array being sorted.
Without sorting, moving the left or right pointer does not reliably increase or decrease the sum.
Mistake 2: Returning Duplicate Triplets
Duplicate values can produce the same triplet multiple times.
Always skip duplicate first elements and repeated left or right values after finding a valid triplet.
Mistake 3: Using the Same Element More Than Once
The triplet must contain values from three different indexes.
The two-pointer solution ensures this by maintaining:
i < left < right
Mistake 4: Moving Both Pointers When the Sum Is Not Zero
When the sum is negative, move only the left pointer forward.
When the sum is positive, move only the right pointer backward.
Moving both pointers unnecessarily can skip valid combinations.
Mistake 5: Ignoring Integer Overflow
The sum of three int values may exceed the int range.
Use long arithmetic to calculate the sum safely.
Mistake 6: Modifying the Original Array Unintentionally
The Arrays.sort() method modifies the array passed to it.
If your application needs to preserve the original array, create a copy before sorting.
10. Frequently Asked Questions
Q1. What is the 3Sum problem in Java?
The 3Sum problem asks you to find all unique triplets of array elements whose sum equals zero.
Q2. What is the best approach to solve 3Sum?
Sorting followed by the two-pointer technique is a common and efficient solution. It has O(n²) time complexity.
Q3. Why is sorting necessary in the two-pointer approach?
Sorting allows the algorithm to increase or decrease the current sum predictably by moving the left or right pointer.
Q4. How do I avoid duplicate triplets?
Skip repeated first elements and repeated left or right values after finding a valid triplet.
Q5. What is the time complexity of 3Sum?
The sorting and two-pointer approach takes O(n²) time in the worst case.
Q6. Can I solve 3Sum using brute force?
Yes. You can use three nested loops to examine all triplets, but the worst-case time complexity is O(n³).
Q7. Can a valid triplet contain duplicate values?
Yes. For example, [-1, -1, 2] is valid if the array contains two occurrences of -1 at different indexes.
Q8. Does the order of triplets matter?
Usually, no. Most coding interview versions accept unique triplets in any order.
Q9. Can the original array remain unchanged?
Yes. The recommended program copies the original array before sorting, so the input is preserved.
Q10. How is 3Sum related to Two Sum?
3Sum can be viewed as repeatedly fixing one value and solving a Two Sum problem for the remaining values.
11. Conclusion
In this tutorial, you learned how to find all unique triplets whose sum equals zero using Java.
- Sorting and Two Pointers: Finds unique triplets efficiently in
O(n²)time. - Brute Force: Checks all possible triplets using three nested loops.
- Duplicate Handling: Ensures that each distinct triplet appears only once.
For Java coding interviews, I recommend mastering the sorting and two-pointer approach. It improves performance significantly over brute force and demonstrates an important array-processing pattern.
Once you understand this problem, practice related questions such as Two Sum, 3Sum Closest, 4Sum, and finding triplets with a given target sum.
12. Official Java Documentation
For additional information about the Java APIs used in this tutorial, refer to the official Oracle documentation:
- Java Arrays Class — Documentation for
Arrays.sort(),Arrays.copyOf(), andArrays.asList(). - Java ArrayList Class — Documentation for storing and managing dynamic Lists.
- Java HashSet Class — Documentation for maintaining unique values.
- Java List Interface — Documentation for ordered collections.
- Java Integer Class — Documentation for integer values and limits.
Continue Learning with Java Guides
Want to take your programming skills to the next level? Explore my practical Udemy courses on Java, Spring Boot, Microservices, Full-Stack Development, Docker, and Generative AI. You can also follow my structured learning roadmaps to become a professional developer.
By Ramesh Fadatare - Udemy Instructor Partner
Comments
Post a Comment
Leave Comment