# 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 from`i + 1`

) and`k`

(starting from the last index). - Move
`j`

forward and`k`

backward until they cross each other, while keeping`i`

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 pointers`j`

and`k`

.

- 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.