Problem Statement:
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.
Examples:
Example 1:
Input:nums = [-1,0,1,2,-1,-4]
Output:[[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.
Example 2:
Input:nums = [0,1,1]
Output:[]
Explanation: The only possible triplet does not sum up to 0.
Example 3:
Input:nums = [0,0,0]
Output:[[0,0,0]]
Explanation: The only possible triplet sums up to 0.
Constraints:
3 <= nums.length <= 3000-10 5 <= nums[i] <= 10 5
Approach
- Sort the array: Sorting helps efficiently avoid duplicates and use the two-pointer technique.
- Fix one number: Loop through each element
nums[i]as a fixed number, and for eachi, find pairs(j, k). - Two-pointer approach:
-
Set two pointers:
left = i + 1right = nums.length - 1- If sum > 0 → move right leftward.
- If sum < 0 → move left rightward.
- If sum == 0 → valid triplet found → store and skip duplicates.
Move them based on the sum:
-
Set two pointers:
- Avoid duplicates: Skip duplicate values for
nums[i]andnums[left]to ensure unique triplets.
Time Complexity:
Time Complexity = O(n2)
Space Complexity:
Space Complexity = O(1)
Dry Run
Input: nums = [-1, 0, 1, 2, -1, -4]
Step 1: Sort the array nums = [-4, -1, -1, 0, 1, 2] Step 2: Begin iterating with index i i = 0 (nums[i] = -4) → nums[0] is not equal to nums[-1] (undefined), so call twoSum(arr, 0, ans) → i = 1, j = 5 sum = -1 + 2 + (-4) = -3 → ++i i = 2, j = 5 → sum = -1 + 2 + (-4) = -3 → ++i i = 3, j = 5 → sum = 0 + 2 + (-4) = -2 → ++i i = 4, j = 5 → sum = 1 + 2 + (-4) = -1 → ++i i = 5, j = 5 → loop ends i = 1 (nums[i] = -1) → nums[1] != nums[0], so call twoSum(arr, 1, ans) → i = 2, j = 5 sum = -1 + 2 + (-1) = 0 → push [-1, 2, -1] ++i, --j → i = 3, j = 4 arr[i] != arr[i-1] (0 != -1) sum = 0 + 1 + (-1) = 0 → push [0, 1, -1] ++i, --j → i = 4, j = 3 → loop ends i = 2 (nums[i] = -1) → nums[2] == nums[1], so skip this iteration to avoid duplicates i = 3 (nums[i] = 0) → nums[3] != nums[2], so call twoSum(arr, 3, ans) → i = 4, j = 5 sum = 1 + 2 + 0 = 3 → --j i = 4, j = 4 → loop ends i = 4, 5 → Remaining indices skipped as at least 3 numbers are required Final ans = [[-1, 2, -1], [0, 1, -1]]
Output: Result: [[-1, -1, 2], [-1, 0, 1]]
Visualisation:
var threeSum = function(nums) {
nums.sort((a, b) => a - b);
let ans = [];
for (let i = 0; i < nums.length; i++) {
if (i === 0 || nums[i] !== nums[i - 1]) {
twoSum(nums, i, ans);
}
}
return ans;
};
var twoSum = function(arr, x, ans) {
let i = x + 1;
let j = arr.length - 1;
while (i < j) {
let sum = arr[i] + arr[j] + arr[x];
if (sum > 0) {
j--;
} else if (sum < 0) {
i++;
} else {
ans.push([arr[i], arr[j], arr[x]]);
i++;
j--;
// Skip duplicates for the second element
while (i < j && arr[i] === arr[i - 1]) {
i++;
}
}
}
};
def twoSum(arr, x, ans):
i = x + 1
j = len(arr) - 1
while i < j:
s = arr[i] + arr[j] + arr[x]
if s > 0:
j -= 1
elif s < 0:
i += 1
else:
ans.append([arr[i], arr[j], arr[x]])
i += 1
j -= 1
while i < j and arr[i] == arr[i - 1]:
i += 1
def threeSum(nums):
nums.sort()
ans = []
for i in range(len(nums)):
if i == 0 or nums[i] != nums[i - 1]:
twoSum(nums, i, ans)
return ans
import java.util.*;
public class Solution {
public void twoSum(int[] arr, int x, List> ans) {
int i = x + 1;
int j = arr.length - 1;
while (i < j) {
int sum = arr[i] + arr[j] + arr[x];
if (sum > 0) {
--j;
} else if (sum < 0) {
++i;
} else {
ans.add(Arrays.asList(arr[i], arr[j], arr[x]));
++i;
--j;
while (i < j && arr[i] == arr[i - 1]) ++i;
}
}
}
public List> threeSum(int[] nums) {
Arrays.sort(nums);
List> ans = new ArrayList<>();
for (int i = 0; i < nums.length; ++i) {
if (i == 0 || nums[i] != nums[i - 1]) {
twoSum(nums, i, ans);
}
}
return ans;
}
}
#include <vector>
#include <algorithm>
using namespace std;
void twoSum(vector& arr, int x, vector>& ans) {
int i = x + 1;
int j = arr.size() - 1;
while (i < j) {
int sum = arr[i] + arr[j] + arr[x];
if (sum > 0) {
--j;
} else if (sum < 0) {
++i;
} else {
ans.push_back({arr[i], arr[j], arr[x]});
++i;
--j;
while (i < j && arr[i] == arr[i - 1]) ++i;
}
}
}
vector> threeSum(vector& nums) {
sort(nums.begin(), nums.end());
vector> ans;
for (int i = 0; i < nums.size(); ++i) {
if (i == 0 || nums[i] != nums[i - 1]) {
twoSum(nums, i, ans);
}
}
return ans;
}
#include <stdio.h>
#include <stdlib.h>
int cmp(const void* a, const void* b) {
return (*(int*)a - *(int*)b);
}
void twoSum(int* arr, int n, int x, int*** ans, int* returnSize) {
int i = x + 1;
int j = n - 1;
while (i < j) {
int sum = arr[i] + arr[j] + arr[x];
if (sum > 0) {
--j;
} else if (sum < 0) {
++i;
} else {
(*ans)[*returnSize] = (int*)malloc(3 * sizeof(int));
(*ans)[*returnSize][0] = arr[i];
(*ans)[*returnSize][1] = arr[j];
(*ans)[*returnSize][2] = arr[x];
(*returnSize)++;
++i;
--j;
while (i < j && arr[i] == arr[i - 1]) ++i;
}
}
}
int** threeSum(int* nums, int numsSize, int* returnSize) {
qsort(nums, numsSize, sizeof(int), cmp);
int** ans = (int**)malloc(1000 * sizeof(int*)); // assuming max 1000 triplets
*returnSize = 0;
for (int i = 0; i < numsSize; ++i) {
if (i == 0 || nums[i] != nums[i - 1]) {
twoSum(nums, numsSize, i, &ans, returnSize);
}
}
return ans;
}
using System;
using System.Collections.Generic;
public class Solution {
public void TwoSum(int[] arr, int x, List> ans) {
int i = x + 1;
int j = arr.Length - 1;
while (i < j) {
int sum = arr[i] + arr[j] + arr[x];
if (sum > 0) {
--j;
} else if (sum < 0) {
++i;
} else {
ans.Add(new List { arr[i], arr[j], arr[x] });
++i;
--j;
while (i < j && arr[i] == arr[i - 1]) ++i;
}
}
}
public IList> ThreeSum(int[] nums) {
Array.Sort(nums);
List> ans = new List>();
for (int i = 0; i < nums.Length; ++i) {
if (i == 0 || nums[i] != nums[i - 1]) {
TwoSum(nums, i, ans);
}
}
return ans;
}
}
