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
Java
C++
Python
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) {
res.add(Arrays.asList(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++;
}
}
}
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.