The threeSum problem is a classic question that aims to find all unique triplets in an array that add up to zero. Given an integer array nums, the goal is to return a list of lists where each list represents a unique triplet that satisfies this condition. Solving this problem optimally requires avoiding duplicates and keeping the solution efficient in both time and space complexity.
Chosen Algorithm and Data Structure
For an optimal solution, we use the two-pointer technique in combination with sorting. Sorting allows us to efficiently manage duplicates and enables the two-pointer approach to find pairs that sum to a target value in O(n) time. This method reduces time complexity significantly from O(n^3) (brute force) to O(n^2).
• Two-pointer pattern: After sorting, we can fix one number and use two pointers to find the remaining two numbers that sum to the target.
• Sorting: Sorting the array enables easy duplicate handling by comparing adjacent elements, allowing us to skip duplicates.
The two-pointer technique works well for problems involving pairs or triplets that meet a sum condition, especially if duplicates need to be avoided. Problems that can benefit from:
• Sorting as a preprocessing step.
• Reducing nested loops using pointers.
• Identifying unique combinations in sorted sequences.
are well-suited for the two-pointer pattern.
This strategy is chosen because it efficiently narrows down the search space, reducing time complexity while preventing duplicate results. Compared to brute force, this approach has:
• Better time complexity: The two-pointer method reduces the complexity to O(n^2).
• Lower space complexity: Sorting in place with pointers requires only minimal additional memory.
Algorithm Steps
1. Initialize a Set result to store unique triplets that sum up to zero.
2. Iterate through nums with index i from 0 to nums.length – 2, choosing each element nums[i] as the first element of a potential triplet.
3. Create a Set seen to keep track of numbers needed to complete a valid triplet.
4. Nested Loop: For each i, iterate j from i + 1 to nums.length, treating nums[j] as the second element.
5. Calculate the complement: Set complement = -nums[i] – nums[j] to find the third number that, with nums[i] and nums[j], sums to zero.
6. Check for complement in seen:
• If found, create a triplet [a, b, c] sorted in ascending order and add it to result to avoid duplicates.
• Add nums[j] to seen to track potential complements.
7. Return the list of unique triplets by converting result to a List.
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Set<List<Integer>> result = new HashSet<>();
for (int i = 0; i < nums.length - 2; i++) {
Set<Integer> seen = new HashSet<>();
for (int j = i + 1; j < nums.length; j++) {
int complement = -nums[i] - nums[j];
if (seen.contains(complement)) {
int a = nums[i];
int b = nums[j];
int c = complement;
List<Integer> list = Arrays.asList(Math.min(a, Math.min(b, c)),
a + b + c - Math.min(a, Math.min(b,c)) - Math.max(a, Math.max(b, c)),
Math.max(a, Math.max(b, c)));
result.add(list);
}
seen.add(nums[j]);
}
}
return new ArrayList<>(result);
}
}Line By Line Explanation
- Initialization of the result Set:
Set<List<Integer>> result = new HashSet<>();• result is a Set of lists, where each list contains three integers representing a triplet that sums up to zero.
• Using a Set instead of a List ensures that only unique triplets are stored, automatically preventing duplicates.
2. Outer Loop
for (int i = 0; i < nums.length - 2; i++) {• The outer loop iterates over the array up to the third-last element (nums.length – 2) because each triplet requires three elements.
• i is the index of the first element in the current triplet being considered.
3. Set Initialization For Each I
Set<Integer> seen = new HashSet<>();• For each i, we initialize a new HashSet called seen.
• seen keeps track of elements in nums that have been processed in the inner loop for the current i. This helps us quickly check if the required complement for a triplet already exists.
4. Inner Loop
for (int j = i + 1; j < nums.length; j++) {• The inner loop iterates from i + 1 to the end of the array.
• j is the index of the second element in the triplet.
5. Calculating Complement
int complement = -nums[i] - nums[j];• For the current values nums[i] and nums[j], the complement is calculated as -nums[i] – nums[j].
• If we find an element in seen that equals this complement, then nums[i], nums[j], and the complement form a valid triplet that sums up to zero.
6. Checking Complement Exists
if (seen.contains(complement)) {• This line checks if the complement is in seen.
• If true, then a zero-sum triplet exists: nums[i] + nums[j] + complement = 0.
7. Add Triplet
int a = nums[i];
int b = nums[j];
int c = complement;
List<Integer> list = Arrays.asList(
Math.min(a, Math.min(b, c)),
a + b + c - Math.min(a, Math.min(b, c)) - Math.max(a, Math.max(b, c)),
Math.max(a, Math.max(b, c))
);
result.add(list);• The triplet values a, b, and c are calculated, where c is the complement.
• We sort the values in ascending order using Math.min and Math.max functions, ensuring that triplets are always stored in the same order.
• The sorted triplet is added to result, which only stores unique lists.
8. Adding to seen
seen.add(nums[j]);
• The current value nums[j] is added to the seen set, so it can be used as a potential complement for future elements in the same inner loop iteration.
9. Return Result
return new ArrayList<>(result);
• Finally, we convert the Set result to a List and return it.
Why This Code Works
This method is efficient because it reduces time complexity to O(n^2) by eliminating unnecessary checks and leveraging sorted data for better search strategies. It avoids the high space complexity of storing duplicate triplets and maintains a minimal, constant space overhead beyond the sorted array.
