Why is Sorting Necessary?
Sorting the array simplifies the process of eliminating duplicates and enables the use of the two-pointer technique efficiently. Once the array is sorted, we can fix one element (say a) and use a two-pointer approach to find b and c such that π + π + π = 0.
Sorting also ensures that duplicate values are adjacent, making it easier to skip repeated elements and avoid generating duplicate triplets.
π Algorithm 1: Sort + Two Pointers
- (1) Sort the array.
- (2) Iterate through the array with index i, treating
nums[i]as the fixed element a. - (3) For each
a = nums[i], use two pointers:- left starting at i + 1
- right starting at the end of the array
- (4) Adjust left and right based on the sum π + π + π :
- If the sum is greater than 0, move right leftward to reduce the total.
- If the sum is less than 0, move left rightward to increase the total.
- If the sum is exactly 0, store the triplet and adjust both pointers to find the next unique pair.
Special Considerations
Scenario 1: Skipping Duplicate a Values
If we encounter the same value for a as in the previous iteration, we can skip it because any triplets including this a have already been considered. This is implemented as:
if (i > 0 && nums[i] == nums[i - 1]) continue;
This ensures that, for example, when the sorted array contains [-10, -10, -10, β¦], we only process the first -10 as a, avoiding duplicate results like [-10, 5, 5] being added multiple times.
Scenario 2: Skipping Duplicate b and c Values
After finding a valid triplet, we want to move both pointers inward to continue searching for other valid pairs.
However, we must avoid adding the same triplet multiple times due to duplicate values in the array. To do this, we skip over duplicate values for both left and right, but only after storing a valid triplet. The logic is:
while (left < right && nums[left] == nums[left - 1]) left++;
while (left < right && nums[right] == nums[right + 1]) right--;
This approach:
- Preserves the leftmost and rightmost occurrence of the duplicate values (to form the valid triplet),
- Skips any middle duplicates to avoid redundant results.
Solution
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
quickSort(nums, 0, nums.length - 1);
int n = nums.length;
List<List<Integer>> res = new ArrayList<>();
for(int i = 0; i < n - 2; i++){
//skip duplicate 'a' values
if(i > 0 && nums[i] == nums[i-1]) continue;
int left = i+1, right = n-1, a = nums[i];
while(left < right){
int b = nums[left], c = nums[right];
if(a + b + c == 0){
res.add(Arrays.asList(a,b,c));
left++;
right--;
// skip duplicate 'b' and 'c' Values
while(left < right && nums[left] == nums[left-1]) left++;
while(left < right && nums[right] == nums[right+1]) right--;
}else if(a + b + c < 0){
left++;
}else{
right--;
}
}
}
return res;
}
public void quickSort(int[] nums, int left, int right) {
if (left >= right) return;
int pivotIndex = partition(nums, left, right);
quickSort(nums, left, pivotIndex - 1);
quickSort(nums, pivotIndex + 1, right);
}
private int partition(int[] nums, int left, int right) {
int pivot = nums[right];
int i = left - 1;
for (int j = left; j < right; j++) {
if (nums[j] <= pivot) {
i++;
swap(nums, i, j);
}
}
swap(nums, i + 1, right);
return i + 1;
}
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
Time Complexity: O(N^2)
The outer loop runs O(N) times, and for each iteration, the two-pointer search runs in O(N) time in the worst case.
Space Complexity: O(log(N))
Ignoring the space used to store the result, the only additional space is used for sorting, which typically requires O(logN) space for the recursion stack in quicksort (depending on implementation).
π Algorithm 2: Sort + Hash Map-Based Search
Core Idea:
- This approach also begins by sorting the input array
- Since weβre looking for triplets
(a,b,c)such that a+b+c=0, we can rearrange the equation to find the third element: c = β(a+b) - To efficiently check whether such a c exists in the array and ensure it appears after both a and b (i.e., avoiding duplicates like
[a,b,c]and[a,c,b]), we use a HashMap<Integer, Integer> to store:- Key: the value of an element
- Value: the last index at which this value appears in the sorted array
- This way, we can directly look up whether a target value c exists after b.
Special Considerations
Scenario 1: Skipping Duplicate a Values
Skip duplicate a values in the outer loop to prevent redundant triplets (same as before).
Scenario 2: Skipping Duplicate b Values
Skip duplicate b values within the inner loop to avoid results like [-10,5,5,5,5] being generated multiple times from different b positions.
Scenario 3: map.get(c) > j to ensure canonical Triplet order
Since we only store the last occurrence of each number, we cannot know all positions where a value appears. So the only way to safely ensure that c is used after b is by checking:
if (map.containsKey(c) && map.get(c) > j)
It enforces that the indices of a, b, and c are strictly increasing, which prevents permutations like [a, b, c] and [a, c, b] from being added as separate results.
Solution
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
quickSort(nums, 0, nums.length - 1);
int n = nums.length;
List<List<Integer>> res = new ArrayList<>();
Map<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < n; i++){
map.put(nums[i], i);
}
for(int i = 0; i < n - 2; i++){
int a = nums[i];
// skip duplicate 'a' values
if(i - 1 >= 0 && nums[i] == nums[i-1]) continue;
for(int j = i + 1; j < n; j++){
// skip duplicate 'b' Values
if(j > i+1 && nums[j] == nums[j - 1]) continue;
int b = nums[j];
int c = -a - b;
//map.get(c) > j ensures that the index of c is after b
if(map.containsKey(c) && map.get(c) > j){
res.add(Arrays.asList(a,b,c));
}
}
map.remove(a);
}
return res;
}
public void quickSort(int[] nums, int left, int right){
//!!!should be left >= right, instead of left == right
if(left >= right) return;
int i = partition(nums, left, right);
quickSort(nums, left, i - 1);
quickSort(nums, i + 1, right);
}
private static int partition(int[] nums, int left, int right){
int i = left, j = right, pivot = nums[right];
while(i <= j){
while(i <= j && nums[i] < pivot) i++;
while(i <= j && nums[j] >= pivot) j--;
//Two pointers pause
// i points to the element that is >pivot => swap(i, j);
if(i < j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
nums[right] = nums[i];
nums[i] = pivot;
return i;
}
}
**Time Complexity:** O(N^2)
The outer and inner loops both run in linear time in the worst case, and map lookups are O(1).
**Space Complexity:** O(N)
For the map storing all elements and their last occurrence.