3Sum

Medium Blind 75 Top 250

Associated Patterns

Interviewed At (Company Tags)

AmazonMetaGoogleMicrosoftAdobe

Problem Description

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

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

Example 2:

Input: nums = [0,1,1] Output: []

Example 3:

Input: nums = [0,0,0] Output: [[0,0,0]]

Constraints

3 ≤ nums.length ≤ 3000
-10⁵ ≤ nums[i] ≤ 10⁵

Fix One Number and Reduce to Two Sum

Three nested loops is O(n³) and generates duplicates. Fix one number by iterating i, then reduce the remaining problem to Two Sum on a sorted subarray, which two pointers solve in O(n). That gets you to O(n²) total.

Sorting first also gives you a free early exit: if nums[i] > 0, no triplet summing to zero can start here (all remaining numbers are non-negative). And sorted duplicates are adjacent, so skipping them becomes a one-line check.

Solution 1: Brute Force with a Set

Three nested loops checking all triplets. Use a set to deduplicate.

import java.util.*;

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

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

#include <vector>
#include <set>
#include <algorithm>

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

Complexity Analysis:

Time Complexity: O(n³). Three nested loops plus sorting each triplet.
Space Complexity: O(n). The result set in the worst case.

Where it breaks: at n = 3000, this is 27 billion operations. Well beyond what passes in any time limit.

Solution 2: Sort + Two Pointers

Sort the array. For each i, use two pointers on nums[i+1..n-1] to find pairs summing to -nums[i]. Skip duplicate values of i and of left/right after finding a triplet to avoid duplicates in the output.

import java.util.*;

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

        for (int i = 0; i < nums.length - 2; i++) {
            if (nums[i] > 0) break; // all remaining sums are positive
            if (i > 0 && nums[i] == nums[i - 1]) continue; // skip duplicate first elements

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

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

        for i in range(len(nums) - 2):
            if nums[i] > 0:
                break  # all remaining sums are positive
            if i > 0 and nums[i] == nums[i - 1]:
                continue  # skip duplicate first elements

            left, right = i + 1, len(nums) - 1
            while left < right:
                s = nums[i] + nums[left] + nums[right]
                if s == 0:
                    result.append([nums[i], nums[left], nums[right]])
                    while left < right and nums[left] == nums[left + 1]: left += 1
                    while left < right and nums[right] == nums[right - 1]: right -= 1
                    left += 1
                    right -= 1
                elif s < 0:
                    left += 1
                else:
                    right -= 1

        return result

#include <vector>
#include <algorithm>

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

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

            int left = i + 1, right = nums.size() - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    result.push_back({nums[i], nums[left], nums[right]});
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    while (left < right && nums[right] == nums[right - 1]) right--;
                    left++; right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return result;
    }
};

Complexity Analysis:

Time Complexity: O(n²). Sorting is O(n log n); the outer loop runs O(n) times and each inner two-pointer scan is O(n).
Space Complexity: O(1) extra, not counting the output.

Where it breaks: if you forget the duplicate-skip logic for left and right after finding a match, you’ll include duplicate triplets in the output. The array [-2, 0, 0, 2, 2] is a good test case: the pair [0, 2] appears twice.

Common Mistakes

Forgetting i > 0 before comparing nums[i] == nums[i-1]. Without this guard, you access nums[-1] on the first iteration.
Skipping duplicates before adding the triplet. The skip loop for left and right advances to the last duplicate, then the left++; right-- at the end moves past it. If you do the skip before the result.add, you’d miss the valid triplet.
Not breaking when nums[i] > 0. Continuing past positive first elements wastes time and can produce wrong results if you mismanage the skip logic.

Frequently Asked Questions

Can you solve 3Sum in better than O(n²)? No known algorithm solves 3Sum in better than O(n²) for the general case. It’s conjectured to be a hard lower bound.

What if the array has fewer than 3 elements? The constraint guarantees n >= 3, so you don’t need to handle this.

How does this extend to 4Sum? Add another outer loop fixing a second element, reducing it to a Two Sum inside. That gives O(n³). The same skip-duplicate logic applies at each level.