Triplet Sum to Zero

Input: [-3, 0, 1, 2, -1, 1, -2]
Output: [-3, 1, 2], [-2, 0, 2], [-2, 1, 1], [-1, 0, 1]
Explanation: There are four unique triplets whose sum is equal to zero.
Input: [-5, 2, -1, -2, 3]
Output: [[-5, 2, 3], [-2, -1, 3]]
Explanation: There are two unique triplets whose sum is equal to zero.

Solution

function search_triplets(arr) {
arr.sort((a, b) => a - b);
const triplets = [];
for (let i = 0; i < arr.length; i++) {
if (i > 0 && arr[i] === arr[i - 1]) { // skip same element to avoid duplicate triplets
continue;
}
search_pair(arr, -arr[i], i + 1, triplets);
}
return triplets;
}

function search_pair(arr, target_sum, left, triplets) {
let right = arr.length - 1; while (left < right) {
const current_sum = arr[left] + arr[right];
if (current_sum === target_sum) { // found the triplet
triplets.push([-target_sum, arr[left], arr[right]]);
left += 1;
right -= 1;
while (left < right && arr[left] === arr[left - 1]) {
left += 1; // skip same element to avoid duplicate triplets }
while (left < right && arr[right] === arr[right + 1]) {
right -= 1; // skip same element to avoid duplicate triplets
}
} else if (target_sum > current_sum) {
left += 1; // we need a pair with a bigger sum
} else {
right -= 1; // we need a pair with a smaller sum
}
}
}
console.log(search_triplets([-3, 0, 1, 2, -1, 1, -2])); console.log(search_triplets([-5, 2, -1, -2, 3]));Output[ [ -3, 1, 2 ], [ -2, 0, 2 ], [ -2, 1, 1 ], [ -1, 0, 1 ] ]
[ [ -5, 2, 3 ], [ -2, -1, 3 ] ]

Time complexity

--

--

--

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

IndexedDb operation in electron app — Part 2

React.js for beginners

Web performance

https://docs.google.com/document/d/1F7fYCf86BAspU3Vhf4cfjogsBKY0rB2Xd8WiuiEzb7k/edit?usp=drivesdk

Types of constant declaration in programming languages.

React Navbar Transition

Pagination in Rails: The Setup

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
SunJet Liu

SunJet Liu

More from Medium

Digitizing actual SoD violation Detection; The role of technology in compliance

My Pet Peeve #30: Home Based Learning

We need utopian biotoopias | Peeter Laurits

Fundamental of microservices