15. 3Sum - Explanation

Description

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] where nums[i] + nums[j] + nums[k] == 0, and the indices i, j and k are all distinct.

The output should not contain any duplicate triplets. You may return the output and the triplets in any order.

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

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 <= 1000
-10^5 <= nums[i] <= 10^5

Topics

Recommended Time & Space Complexity

You should aim for a solution with O(n^2) time and O(1) space, where n is the size of the input array.

Hint 1

A brute force solution would be to check for every triplet in the array. This would be an O(n^3) solution. Can you think of a better way?

Hint 2

Can you think of an algorithm after sorting the input array? What can we observe by rearranging the given equation in the problem?

Hint 3

We can iterate through nums with index i and get nums[i] = -(nums[j] + nums[k]) after rearranging the equation, making -nums[i] = nums[j] + nums[k]. For each index i, we should efficiently calculate the j and k pairs without duplicates. Which algorithm is suitable to find j and k pairs?

Hint 4

To efficiently find the j and k pairs, we run the two pointer approach on the elements to the right of index i as the array is sorted. When we run two pointer algorithm, consider j and k as pointers (j is at left, k is at right) and target = -nums[i], if the current sum num[j] + nums[k] < target then we need to increase the value of current sum by incrementing j pointer. Else if the current sum num[j] + nums[k] > target then we should decrease the value of current sum by decrementing k pointer. How do you deal with duplicates?

Hint 5

When the current sum nums[j] + nums[k] == target add this pair to the result. We can move j or k pointer until j < k and the pairs are repeated. This ensures that no duplicate pairs are added to the result.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Sorting - Sorting the array enables efficient duplicate handling and two-pointer technique
Two pointers - The optimal solution uses two pointers to find pairs that sum to a target
Hash maps - An alternative approach uses hash maps for O(1) lookups
Handling duplicates - Skipping duplicate values to avoid repeated triplets in the result

1. Brute Force

Intuition

The brute-force approach simply tries every possible triplet.
Since we check all combinations (i, j, k) with i < j < k, we are guaranteed to find all sets of three numbers that sum to zero.
Sorting helps keep the triplets in order and makes it easier to avoid duplicates by storing them in a set.

Algorithm

Sort the array to make handling duplicates easier.
Create an empty set res to store unique triplets.
Use three nested loops:
- For each i,
- For each j > i,
- For each k > j,
  - Check if nums[i] + nums[j] + nums[k] == 0.
  - If true, add the sorted triplet to the set.
Convert the set of tuples back into a list of lists.
Return the result.

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = set()
        nums.sort()
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                for k in range(j + 1, len(nums)):
                    if nums[i] + nums[j] + nums[k] == 0:
                        tmp = [nums[i], nums[j], nums[k]]
                        res.add(tuple(tmp))
        return [list(i) for i in res]

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Set<List<Integer>> res = new HashSet<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        List<Integer> tmp = Arrays.asList(nums[i], nums[j], nums[k]);
                        res.add(tmp);
                    }
                }
            }
        }
        return new ArrayList<>(res);
    }
}

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        set<vector<int>> res;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); i++) {
            for (int j = i + 1; j < nums.size(); j++) {
                for (int k = j + 1; k < nums.size(); k++) {
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        res.insert({nums[i], nums[j], nums[k]});
                    }
                }
            }
        }
        return vector<vector<int>>(res.begin(), res.end());
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @return {number[][]}
     */
    threeSum(nums) {
        const res = new Set();
        nums.sort((a, b) => a - b);
        for (let i = 0; i < nums.length; i++) {
            for (let j = i + 1; j < nums.length; j++) {
                for (let k = j + 1; k < nums.length; k++) {
                    if (nums[i] + nums[j] + nums[k] === 0) {
                        res.add(JSON.stringify([nums[i], nums[j], nums[k]]));
                    }
                }
            }
        }
        return Array.from(res).map((item) => JSON.parse(item));
    }
}

public class Solution {
    public List<List<int>> ThreeSum(int[] nums) {
        HashSet<Tuple<int, int, int>> uniqueTriplets = new HashSet<Tuple<int, int, int>>();
        List<List<int>> res = new List<List<int>>();
        Array.Sort(nums);

        for (int i = 0; i < nums.Length; i++) {
            for (int j = i + 1; j < nums.Length; j++) {
                for (int k = j + 1; k < nums.Length; k++) {
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        var triplet = Tuple.Create(nums[i], nums[j], nums[k]);
                        uniqueTriplets.Add(triplet);
                    }
                }
            }
        }

        foreach (var triplet in uniqueTriplets) {
            res.Add(new List<int> { triplet.Item1, triplet.Item2, triplet.Item3 });
        }
        return res;
    }
}

class Solution {
    fun threeSum(nums: IntArray): List<List<Int>> {
        val res = HashSet<List<Int>>()
        nums.sort()
        for (i in nums.indices) {
            for (j in i + 1 until nums.size) {
                for (k in j + 1 until nums.size) {
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        res.add(listOf(nums[i], nums[j], nums[k]))
                    }
                }
            }
        }
        return res.map { it.toList() }
    }
}

class Solution {
    func threeSum(_ nums: [Int]) -> [[Int]] {
        var res = Set<[Int]>()
        let nums = nums.sorted()

        for i in 0..<nums.count {
            for j in (i + 1)..<nums.count {
                for k in (j + 1)..<nums.count {
                    if nums[i] + nums[j] + nums[k] == 0 {
                        let tmp = [nums[i], nums[j], nums[k]]
                        res.insert(tmp)
                    }
                }
            }
        }
        return Array(res)
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 3)$
Space complexity: $O(m)$

Where $m$ is the number of triplets and $n$ is the length of the given array.

2. Hash Map

Intuition

After sorting the array, we can fix two numbers and look for the third number that completes the triplet.
To do this efficiently, we use a hash map that stores how many times each number appears.
As we pick the first and second numbers, we temporarily reduce their counts in the map so we don't reuse them.
Then we check whether the needed third value still exists in the map.
Sorting also helps us skip duplicates easily so we only add unique triplets.

Algorithm

Sort the array to organize duplicates and allow easy skipping.
Build a frequency map count for all numbers.
Initialize an empty list res for storing valid triplets.
Loop through each index i:
- Decrease the count of nums[i] (so it won't be reused).
- Skip duplicates of the first element.
- Loop through each index j > i:
  - Decrease the count of nums[j].
  - Skip duplicates of the second element.
  - Compute the needed third value:
    target = -(nums[i] + nums[j])
  - If target still has a positive count, add the triplet.
- After finishing all js, restore the counts for the second loop by adding back the decremented values.
Return res containing all found triplets.

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        count = defaultdict(int)
        for num in nums:
            count[num] += 1

        res = []
        for i in range(len(nums)):
            count[nums[i]] -= 1
            if i and nums[i] == nums[i - 1]:
                continue

            for j in range(i + 1, len(nums)):
                count[nums[j]] -= 1
                if j - 1 > i and nums[j] == nums[j - 1]:
                    continue
                target = -(nums[i] + nums[j])
                if count[target] > 0:
                    res.append([nums[i], nums[j], target])

            for j in range(i + 1, len(nums)):
                count[nums[j]] += 1
        return res

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        Map<Integer, Integer> count = new HashMap<>();
        for (int num : nums) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }

        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            count.put(nums[i], count.get(nums[i]) - 1);
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            for (int j = i + 1; j < nums.length; j++) {
                count.put(nums[j], count.get(nums[j]) - 1);
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;

                int target = -(nums[i] + nums[j]);
                if (count.getOrDefault(target, 0) > 0) {
                    res.add(Arrays.asList(nums[i], nums[j], target));
                }
            }

            for (int j = i + 1; j < nums.length; j++) {
                count.put(nums[j], count.get(nums[j]) + 1);
            }
        }
        return res;
    }
}

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        unordered_map<int, int> count;
        for (int num : nums) {
            count[num]++;
        }

        vector<vector<int>> res;
        for (int i = 0; i < nums.size(); i++) {
            count[nums[i]]--;
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            for (int j = i + 1; j < nums.size(); j++) {
                count[nums[j]]--;
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;

                int target = -(nums[i] + nums[j]);
                if (count[target] > 0) {
                    res.push_back({nums[i], nums[j], target});
                }
            }

            for (int j = i + 1; j < nums.size(); j++) {
                count[nums[j]]++;
            }
        }

        return res;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @return {number[][]}
     */
    threeSum(nums) {
        nums.sort((a, b) => a - b);
        const count = new Map();
        for (let num of nums) {
            count.set(num, (count.get(num) || 0) + 1);
        }

        const res = [];
        for (let i = 0; i < nums.length; i++) {
            count.set(nums[i], count.get(nums[i]) - 1);
            if (i > 0 && nums[i] === nums[i - 1]) continue;

            for (let j = i + 1; j < nums.length; j++) {
                count.set(nums[j], count.get(nums[j]) - 1);
                if (j > i + 1 && nums[j] === nums[j - 1]) continue;

                const target = -(nums[i] + nums[j]);
                if (count.get(target) > 0) {
                    res.push([nums[i], nums[j], target]);
                }
            }

            for (let j = i + 1; j < nums.length; j++) {
                count.set(nums[j], count.get(nums[j]) + 1);
            }
        }
        return res;
    }
}

public class Solution {
    public List<List<int>> ThreeSum(int[] nums) {
        Array.Sort(nums);
        Dictionary<int, int> count = new Dictionary<int, int>();
        foreach (int num in nums) {
            if (!count.ContainsKey(num)) {
                count[num] = 0;
            }
            count[num]++;
        }

        List<List<int>> res = new List<List<int>>();
        for (int i = 0; i < nums.Length; i++) {
            count[nums[i]]--;
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            for (int j = i + 1; j < nums.Length; j++) {
                count[nums[j]]--;
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;

                int target = -(nums[i] + nums[j]);
                if (count.ContainsKey(target) && count[target] > 0) {
                    res.Add(new List<int> { nums[i], nums[j], target });
                }
            }

            for (int j = i + 1; j < nums.Length; j++) {
                count[nums[j]]++;
            }
        }

        return res;
    }
}

func threeSum(nums []int) [][]int {
    sort.Ints(nums)
    count := make(map[int]int)
    for _, num := range nums {
        count[num]++
    }

    var res [][]int
    for i := 0; i < len(nums); i++ {
        count[nums[i]]--
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }

        for j := i + 1; j < len(nums); j++ {
            count[nums[j]]--
            if j > i+1 && nums[j] == nums[j-1] {
                continue
            }
            target := -(nums[i] + nums[j])
            if count[target] > 0 {
                res = append(res, []int{nums[i], nums[j], target})
            }
        }

        for j := i + 1; j < len(nums); j++ {
            count[nums[j]]++
        }
    }

    return res
}

class Solution {
    fun threeSum(nums: IntArray): List<List<Int>> {
        nums.sort()
        val count = HashMap<Int, Int>()
        for (num in nums) {
            count[num] = count.getOrDefault(num, 0) + 1
        }

        val res = mutableListOf<List<Int>>()
        for (i in nums.indices) {
            count[nums[i]] = count[nums[i]]!! - 1
            if (i > 0 && nums[i] == nums[i - 1]) continue

            for (j in i + 1 until nums.size) {
                count[nums[j]] = count[nums[j]]!! - 1
                if (j > i + 1 && nums[j] == nums[j - 1]) continue

                val target = -(nums[i] + nums[j])
                if (count.getOrDefault(target, 0) > 0) {
                    res.add(listOf(nums[i], nums[j], target))
                }
            }

            for (j in i + 1 until nums.size) {
                count[nums[j]] = count[nums[j]]!! + 1
            }
        }

        return res
    }
}

class Solution {
    func threeSum(_ nums: [Int]) -> [[Int]] {
        var nums = nums.sorted()
        var count = [Int: Int]()
        for num in nums {
            count[num, default: 0] += 1
        }

        var res = [[Int]]()
        for i in 0..<nums.count {
            count[nums[i]]! -= 1
            if i > 0 && nums[i] == nums[i - 1] {
                continue
            }

            for j in (i + 1)..<nums.count {
                count[nums[j]]! -= 1
                if j > i + 1 && nums[j] == nums[j - 1] {
                    continue
                }
                let target = -(nums[i] + nums[j])
                if let cnt = count[target], cnt > 0 {
                    res.append([nums[i], nums[j], target])
                }
            }

            for j in (i + 1)..<nums.count {
                count[nums[j]]! += 1
            }
        }
        return res
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$

3. Two Pointers

Intuition

After sorting the array, we can fix one number and then search for the other two using the two-pointer technique.
Sorting helps in two ways:

It lets us skip duplicates easily.
It ensures that moving the left or right pointer will increase or decrease the sum in a predictable way.

For each fixed number a, we place two pointers:

l starts just after i,
r starts at the end.

If the current sum is too large, we move r left to reduce it.
If the sum is too small, we move l right to increase it.
When the sum is exactly zero, we record the triplet and skip duplicates.

Algorithm

Sort the array to handle duplicates and enable two-pointer logic.
Loop through the array using index i:
- Let a = nums[i].
- If a > 0, break (all remaining numbers are positive).
- Skip duplicate values for the first number.
Set two pointers:
- l = i + 1
- r = len(nums) - 1
While l < r:
- Compute threeSum = a + nums[l] + nums[r].
- If threeSum > 0, move r left.
- If threeSum < 0, move l right.
- If threeSum == 0:
  - Add the triplet to the result.
  - Move both pointers inward.
  - Skip duplicates at the left pointer.
Return the list of all valid triplets.

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()

        for i, a in enumerate(nums):
            if a > 0:
                break

            if i > 0 and a == nums[i - 1]:
                continue

            l, r = i + 1, len(nums) - 1
            while l < r:
                threeSum = a + nums[l] + nums[r]
                if threeSum > 0:
                    r -= 1
                elif threeSum < 0:
                    l += 1
                else:
                    res.append([a, nums[l], nums[r]])
                    l += 1
                    r -= 1
                    while nums[l] == nums[l - 1] and l < r:
                        l += 1

        return res

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) break;
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            int l = i + 1, r = nums.length - 1;
            while (l < r) {
                int sum = nums[i] + nums[l] + nums[r];
                if (sum > 0) {
                    r--;
                } else if (sum < 0) {
                    l++;
                } else {
                    res.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    l++;
                    r--;
                    while (l < r && nums[l] == nums[l - 1]) {
                        l++;
                    }
                }
            }
        }
        return res;
    }
}

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;

        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] > 0) break;
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            int l = i + 1, r = nums.size() - 1;
            while (l < r) {
                int sum = nums[i] + nums[l] + nums[r];
                if (sum > 0) {
                    r--;
                } else if (sum < 0) {
                    l++;
                } else {
                    res.push_back({nums[i], nums[l], nums[r]});
                    l++;
                    r--;
                    while (l < r && nums[l] == nums[l - 1]) {
                        l++;
                    }
                }
            }
        }
        return res;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @return {number[][]}
     */
    threeSum(nums) {
        nums.sort((a, b) => a - b);
        const res = [];

        for (let i = 0; i < nums.length; i++) {
            if (nums[i] > 0) break;
            if (i > 0 && nums[i] === nums[i - 1]) continue;

            let l = i + 1;
            let r = nums.length - 1;
            while (l < r) {
                const sum = nums[i] + nums[l] + nums[r];
                if (sum > 0) {
                    r--;
                } else if (sum < 0) {
                    l++;
                } else {
                    res.push([nums[i], nums[l], nums[r]]);
                    l++;
                    r--;
                    while (l < r && nums[l] === nums[l - 1]) {
                        l++;
                    }
                }
            }
        }
        return res;
    }
}

public class Solution {
    public List<List<int>> ThreeSum(int[] nums) {
        Array.Sort(nums);
        List<List<int>> res = new List<List<int>>();

        for (int i = 0; i < nums.Length; i++) {
            if (nums[i] > 0) break;
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            int l = i + 1, r = nums.Length - 1;
            while (l < r) {
                int sum = nums[i] + nums[l] + nums[r];
                if (sum > 0) {
                    r--;
                } else if (sum < 0) {
                    l++;
                } else {
                    res.Add(new List<int> {nums[i], nums[l], nums[r]});
                    l++;
                    r--;
                    while (l < r && nums[l] == nums[l - 1]) {
                        l++;
                    }
                }
            }
        }
        return res;
    }
}

func threeSum(nums []int) [][]int {
    res := [][]int{}
    sort.Ints(nums)

    for i := 0; i < len(nums); i++ {
        a := nums[i]
        if a > 0 {
            break
        }
        if i > 0 && a == nums[i-1] {
            continue
        }

        l, r := i+1, len(nums)-1
        for l < r {
            threeSum := a + nums[l] + nums[r]
            if threeSum > 0 {
                r--
            } else if threeSum < 0 {
                l++
            } else {
                res = append(res, []int{a, nums[l], nums[r]})
                l++
                r--
                for l < r && nums[l] == nums[l-1] {
                    l++
                }
            }
        }
    }

    return res
}

class Solution {
    fun threeSum(nums: IntArray): List<List<Int>> {
        val res = mutableListOf<List<Int>>()
        nums.sort()

        for (i in nums.indices) {
            val a = nums[i]
            if (a > 0) break
            if (i > 0 && a == nums[i - 1]) continue

            var l = i + 1
            var r = nums.size - 1
            while (l < r) {
                val threeSum = a + nums[l] + nums[r]
                when {
                    threeSum > 0 -> r--
                    threeSum < 0 -> l++
                    else -> {
                        res.add(listOf(a, nums[l], nums[r]))
                        l++
                        r--
                        while (l < r && nums[l] == nums[l - 1]) {
                            l++
                        }
                    }
                }
            }
        }

        return res
    }
}

class Solution {
    func threeSum(_ nums: [Int]) -> [[Int]] {
        var res = [[Int]]()
        var nums = nums.sorted()

        for i in 0..<nums.count {
            let a = nums[i]
            if a > 0 {
                break
            }
            if i > 0 && a == nums[i - 1] {
                continue
            }

            var l = i + 1, r = nums.count - 1
            while l < r {
                let threeSum = a + nums[l] + nums[r]
                if threeSum > 0 {
                    r -= 1
                } else if threeSum < 0 {
                    l += 1
                } else {
                    res.append([a, nums[l], nums[r]])
                    l += 1
                    r -= 1
                    while l < r && nums[l] == nums[l - 1] {
                        l += 1
                    }
                }
            }
        }
        return res
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity:
- $O(1)$ or $O(n)$ extra space depending on the sorting algorithm.
- $O(m)$ space for the output list.

Where $m$ is the number of triplets and $n$ is the length of the given array.

Common Pitfalls

Forgetting to Skip Duplicates

A common mistake is not properly skipping duplicate values, which leads to duplicate triplets in the result. After sorting, when you find a valid triplet, you must skip over all identical values for the first element (outer loop) and the left pointer. Failing to do this causes wrong answers on inputs like [-1, -1, 0, 1, 1].

Not Sorting the Array First

The two-pointer approach only works correctly on a sorted array. Without sorting, moving pointers based on sum comparisons does not guarantee you will find all valid triplets. Always sort the input array before applying the two-pointer technique.

Incorrect Early Termination

When the first element nums[i] is positive, all remaining elements are also positive (since the array is sorted), so no triplet can sum to zero. However, incorrectly breaking when nums[i] >= 0 instead of nums[i] > 0 misses cases like [0, 0, 0]. The break condition should be nums[i] > 0, not nums[i] >= 0.