### Problem Statement

Given an array of unsorted numbers, find all unique triplets in it that add up to zero.

### Example:

```Input1: arr: [0, -1, 2, -3, 1]
Output1: [[0, -1, 1], [2, -3, 1]]

Input2: arr: [-3, 0, 1, 2, -1, 1, -2]
Output2: [[-3, 1, 2], [-2, 0, 2], [-2, 1, 1], [-1, 0, 1]]

Explanation: Sum of each triplet is 0.```

### Code

```import java.util.*;

class Innoskrit {

public static List<List<Integer>> uniqueTriplets(int[] arr) {

Arrays.sort(arr);
List<List<Integer>> res = new ArrayList<>();
int n = arr.length;

for(int i = 0; i < n - 2; i++) {
if(i > 0 && arr[i] == arr[i - 1]) {
continue;
}
uniqueTripletsUtil(arr, i, i + 1, n, res);
}

return res;
}

private static void uniqueTripletsUtil(int[] arr, int i, int low, int n,
List<List<Integer>> res) {
int high = n - 1;

while(low < high) {
int sum = arr[i] + arr[low] + arr[high];

if(sum == 0) {
low++;
high--;

while(low < high && arr[low - 1] == arr[low]) {
low++;
}

while(low < high && arr[high] == arr[high + 1]) {
high--;
}
} else if(sum > 0) {
high--;
} else {
low++;
}
}
}

public static void main(String[] args) {

int arr[] = new int[] {0, -1, 2, -3, 1};
List<List<Integer>> ans = Innoskrit.uniqueTriplets(arr);
System.out.println(ans);

arr = new int[] {-3, 0, 1, 2, -1, 1, -2};
ans = Innoskrit.uniqueTriplets(arr);
System.out.println(ans);
}
}```
```#include<bits/stdc++.h>
using namespace std;

class Innoskrit {

public:
static vector<vector<int>> uniqueTriplets(vector<int> &arr) {

sort(arr.begin(), arr.end());
vector<vector<int>> res;
int n = arr.size();

for(int i = 0; i < n - 2; i++) {
if(i > 0 && arr[i] == arr[i - 1]) {
continue;
}
uniqueTripletsUtil(arr, i, i + 1, n, res);
}
return res;
}

private:
static void uniqueTripletsUtil(vector<int> &arr, int i, int low, int n,
vector<vector<int>> &res) {
int high = n - 1;

while(low < high) {
int sum = arr[i] + arr[low] + arr[high];

if(sum == 0) {
res.push_back({arr[i], arr[low], arr[high]});
low++;
high--;

while(low < high && arr[low - 1] == arr[low]) {
low++;
}

while(low < high && arr[high] == arr[high + 1]) {
high--;
}
} else if(sum > 0) {
high--;
} else {
low++;
}
}
}
};

// Just for printing
void printResult(vector<vector<int>> &ans) {
cout<<"[";
for(int i = 0; i < ans.size(); i++) {
cout<<"[";
for(int j = 0; j < ans[i].size(); j++) {
if(j != ans[i].size() - 1) {
cout<<ans[i][j]<<", ";
} else {
cout<<ans[i][j];
}
}

if(i != ans.size() - 1)
cout<<"], ";
else
cout<<"]";
}
cout<<"]\n";
}

int main() {

vector<int> arr = {0, -1, 2, -3, 1};
vector<vector<int>> ans = Innoskrit::uniqueTriplets(arr);
printResult(ans);

arr = {-3, 0, 1, 2, -1, 1, -2};
ans = Innoskrit::uniqueTriplets(arr);
printResult(ans);
return 0;

}```
```class Innoskrit:

@staticmethod
def unique_triplets(arr):
arr.sort()
res, n = [], len(arr)

for i in range(0, n-1):
if i > 0 and arr[i] == arr[i-1]:
continue
Innoskrit.unique_triplets_util(arr, i, i + 1, n, res);

return res

@staticmethod
def unique_triplets_util(arr, i, low, n, res):
high = n - 1
while low < high:
sum = arr[i] + arr[low] + arr[high]
if sum == 0:
res.append([arr[i], arr[low], arr[high]])
low += 1
high -= 1

while low < high and arr[low - 1] == arr[low]:
low += 1;

while low < high and arr[high] == arr[high + 1]:
high -= 1

elif sum > 0:
high -= 1

else:
low += 1

if __name__ == '__main__':
arr = [0, -1, 2, -3, 1]
ans = Innoskrit.unique_triplets(arr)
print(ans)

arr = [-3, 0, 1, 2, -1, 1, -2]
ans = Innoskrit.unique_triplets(arr)
print(ans)```

### Output:

```[[-3, 1, 2], [-1, 0, 1]]
[[-3, 1, 2], [-2, 0, 2], [-2, 1, 1], [-1, 0, 1]]```

### Time and Space Complexity

Time Complexity: O(N2)
Sorting the array will take O(n log n) and while finding the triplets, for each element we are finding the pair in a sorted array which will take O(N2) time. Hence, the final time complexity is O(N2).

Space Complexity: O(1) if we ignore the output array.