Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

3Sum

MEDIUMProblemSolveExternal Links

Description

Given an integer array nums, find all unique triplets [nums[i], nums[j], nums[k]] such that:

  • i, j, and k are all distinct indices (i ≠ j, i ≠ k, j ≠ k)
  • nums[i] + nums[j] + nums[k] == 0

Return a list of all such triplets. The solution set must not contain duplicate triplets — that is, if two triplets contain the same three values (regardless of order), only one should appear in the result.

The order of the output and the order of elements within each triplet does not matter.

Examples

Example 1

Input: nums = [-1, 0, 1, 2, -1, -4]

Output: [[-1, -1, 2], [-1, 0, 1]]

Explanation: There are three index combinations whose values sum to zero:

  • 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

However, the first and second combinations produce the same set of values {-1, 0, 1}, so only one copy appears. The distinct triplets are [-1, -1, 2] and [-1, 0, 1].

Example 2

Input: nums = [0, 1, 1]

Output: []

Explanation: The only possible triplet is (0, 1, 1), which sums to 0 + 1 + 1 = 2 ≠ 0. No valid triplet exists, so we return an empty list.

Example 3

Input: nums = [0, 0, 0]

Output: [[0, 0, 0]]

Explanation: The only triplet is (0, 0, 0), and 0 + 0 + 0 = 0. Even though all elements are the same, this counts as one unique triplet.

Constraints

  • 3 ≤ nums.length ≤ 3000
  • -10^5 ≤ nums[i] ≤ 10^5

Editorial

Brute Force

Intuition

The most direct way to find all triplets that sum to zero is to try every possible combination of three elements. For each element at index i, we pair it with every element at index j > i, and then with every element at index k > j. If the three values add up to zero, we have found a valid triplet.

To avoid duplicate triplets in the result, we can sort each triplet before adding it, and use a set to track which triplets we have already included.

Think of it like a teacher asking a classroom of students to form groups of three whose jersey numbers add up to zero. The brute force approach has the teacher check every possible group of three students — exhaustive but guaranteed to find all valid groups.

Step-by-Step Explanation

Let's trace through with nums = [-1, 0, 1, 2, -1, -4]:

Step 1: Fix i = 0 (value -1). We need two other elements that sum to 1.

Step 2: Try (i=0, j=1, k=2): -1 + 0 + 1 = 0. Found a triplet! Sort it → [-1, 0, 1]. Add to result set.

Step 3: Try (i=0, j=1, k=3): -1 + 0 + 2 = 1 ≠ 0. Not valid.

Step 4: Try (i=0, j=1, k=4): -1 + 0 + (-1) = -2 ≠ 0. Not valid.

Step 5: Try (i=0, j=1, k=5): -1 + 0 + (-4) = -5 ≠ 0. Not valid.

Step 6: Try (i=0, j=2, k=3): -1 + 1 + 2 = 2 ≠ 0. Not valid.

Step 7: Try (i=0, j=3, k=4): -1 + 2 + (-1) = 0. Found a triplet! Sort it → [-1, -1, 2]. Add to result set.

Step 8: Continue checking all remaining triplets (i=0 with remaining j,k; then i=1,2,3,4 with their j,k). Some produce duplicates of already-found triplets, which the set filters out.

Result: Unique triplets = [[-1, 0, 1], [-1, -1, 2]]. We checked all C(6,3) = 20 triplets to find these.

Brute Force — Checking All Triplet Combinations — Watch how the brute force method tests every possible group of three elements, collecting valid triplets whose sum equals zero.

Algorithm

  1. Initialize an empty set to store unique triplets
  2. For each index i from 0 to n-3:
    • For each index j from i+1 to n-2:
      • For each index k from j+1 to n-1:
        • If nums[i] + nums[j] + nums[k] == 0:
          • Sort the triplet [nums[i], nums[j], nums[k]]
          • Add it to the set (automatically handles duplicates)
  3. Convert the set to a list and return

Code

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        set<vector<int>> resultSet;
        
        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) {
                        vector<int> triplet = {nums[i], nums[j], nums[k]};
                        sort(triplet.begin(), triplet.end());
                        resultSet.insert(triplet);
                    }
                }
            }
        }
        
        return vector<vector<int>>(resultSet.begin(), resultSet.end());
    }
};
class Solution:
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        n = len(nums)
        result_set = set()
        
        for i in range(n - 2):
            for j in range(i + 1, n - 1):
                for k in range(j + 1, n):
                    if nums[i] + nums[j] + nums[k] == 0:
                        triplet = tuple(sorted([nums[i], nums[j], nums[k]]))
                        result_set.add(triplet)
        
        return [list(t) for t in result_set]
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        Set<List<Integer>> resultSet = new HashSet<>();
        
        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) {
                        List<Integer> triplet = new ArrayList<>(Arrays.asList(nums[i], nums[j], nums[k]));
                        Collections.sort(triplet);
                        resultSet.add(triplet);
                    }
                }
            }
        }
        
        return new ArrayList<>(resultSet);
    }
}

Complexity Analysis

Time Complexity: O(n³)

Three nested loops iterate over all possible triplets. The total number of combinations is C(n, 3) = n × (n-1) × (n-2) / 6, which simplifies to O(n³). Sorting each triplet is O(1) since it always has exactly 3 elements.

Space Complexity: O(n) for the result set

In the worst case, the set stores up to O(n²) unique triplets. However, the auxiliary space used during computation (excluding the output) is O(1) beyond the set used for deduplication.

Why This Approach Is Not Efficient

The brute force approach has O(n³) time complexity. With n up to 3000, this means up to ~4.5 × 10^9 operations — far too slow for typical time limits.

The fundamental inefficiency is that once we fix one element, we still do a brute-force O(n²) scan to find the other two. We are not exploiting any structure in the data.

The critical insight for improvement: if the array is sorted, then for a fixed first element, the problem of finding two elements that sum to a specific value becomes a classic Two Sum on a sorted array, which can be solved in O(n) using two pointers instead of O(n²). Sorting the array first costs O(n log n) — a one-time price — but it enables us to reduce the inner search from O(n²) to O(n), bringing the total from O(n³) to O(n²). As a bonus, sorting makes duplicate handling trivial: identical values are adjacent, so we simply skip over repeated values.

Optimal Approach - Sorting + Two Pointers

Intuition

The key observation is that 3Sum can be reduced to multiple instances of 2Sum. If we fix one number nums[i], we need to find two numbers in the rest of the array that sum to -nums[i]. This is exactly the Two Sum problem.

To make the Two Sum search efficient, we first sort the entire array. After sorting, for each fixed nums[i], we place a left pointer just after i and a right pointer at the end of the array. We then apply the two-pointer technique:

  • If nums[left] + nums[right] equals our target (-nums[i]), we found a valid triplet.
  • If the sum is too small, move left rightward to increase it.
  • If the sum is too large, move right leftward to decrease it.

Duplicate handling becomes elegant with sorting. Since identical values sit next to each other:

  • For the outer loop: if nums[i] == nums[i-1], we skip i because we already explored all triplets with that first value.
  • For the inner two pointers: after finding a valid triplet, we skip over duplicate values of left and right to avoid adding the same triplet again.

Imagine lining up numbered cards in ascending order. You pick one card and then use two hands to scan inward from both ends of the remaining cards. If the three cards sum to zero, record it and skip over any identical cards to avoid repeats.

Step-by-Step Explanation

Let's trace through with nums = [-1, 0, 1, 2, -1, -4]:

Step 1: Sort the array → [-4, -1, -1, 0, 1, 2].

Step 2: Fix i = 0 (value -4). Target for two-sum = 4. Set left = 1, right = 5.

Step 3: nums[left] + nums[right] = -1 + 2 = 1. 1 < 4, so move left rightward. left = 2.

Step 4: nums[left] + nums[right] = -1 + 2 = 1. 1 < 4, so move left rightward. left = 3.

Step 5: nums[left] + nums[right] = 0 + 2 = 2. 2 < 4, so move left rightward. left = 4.

Step 6: nums[left] + nums[right] = 1 + 2 = 3. 3 < 4, so move left rightward. left = 5. Now left >= right, so stop inner loop for i=0. No triplet starting with -4 sums to zero.

Step 7: Fix i = 1 (value -1). Target for two-sum = 1. Set left = 2, right = 5.

Step 8: nums[left] + nums[right] = -1 + 2 = 1. 1 == 1! Found triplet [-1, -1, 2]. Add to result.

Step 9: Skip duplicates: move left past duplicate -1 values → left = 3. Move right past duplicate 2 values → right = 4.

Step 10: nums[left] + nums[right] = 0 + 1 = 1. 1 == 1! Found triplet [-1, 0, 1]. Add to result.

Step 11: Skip duplicates: left = 4, right = 3. Now left >= right, so stop inner loop for i=1.

Step 12: i = 2 (value -1). But nums[2] == nums[1] (both -1), so skip this i to avoid duplicate triplets.

Step 13: Fix i = 3 (value 0). Target = 0. left = 4, right = 5. Sum = 1 + 2 = 3 > 0. Move right. right = 4. left >= right, stop.

Step 14: i = 4 would leave only 1 element after it (need at least 2), and i = 5 has none. Stop.

Result: [[-1, -1, 2], [-1, 0, 1]].

Sorting + Two Pointers — Efficient Triplet Search — After sorting the array, we fix one element and use two converging pointers to find pairs that complete a zero-sum triplet. Duplicate skipping ensures unique results.

Algorithm

  1. Sort the array in ascending order
  2. For each index i from 0 to n-3:
    • If i > 0 and nums[i] == nums[i-1], skip (avoid duplicate first elements)
    • If nums[i] > 0, break (no three positive numbers can sum to zero)
    • Set left = i + 1, right = n - 1
    • While left < right:
      • Compute sum = nums[i] + nums[left] + nums[right]
      • If sum == 0: add triplet to result, then skip duplicates for both left and right
      • If sum < 0: increment left (need a larger value)
      • If sum > 0: decrement right (need a smaller value)
  3. Return the result list

Code

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        int n = nums.size();
        sort(nums.begin(), nums.end());
        
        for (int i = 0; i < n - 2; i++) {
            // Skip duplicate first elements
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            
            // Early termination: if smallest is positive, no zero sum possible
            if (nums[i] > 0) break;
            
            int left = i + 1;
            int right = n - 1;
            
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                
                if (sum == 0) {
                    result.push_back({nums[i], nums[left], nums[right]});
                    
                    // Skip duplicate left values
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    // Skip duplicate right values
                    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]]:
        result = []
        n = len(nums)
        nums.sort()
        
        for i in range(n - 2):
            # Skip duplicate first elements
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            
            # Early termination
            if nums[i] > 0:
                break
            
            left = i + 1
            right = n - 1
            
            while left < right:
                total = nums[i] + nums[left] + nums[right]
                
                if total == 0:
                    result.append([nums[i], nums[left], nums[right]])
                    
                    # Skip duplicate left values
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    # Skip duplicate right values
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1
                    
                    left += 1
                    right -= 1
                elif total < 0:
                    left += 1
                else:
                    right -= 1
        
        return result
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        int n = nums.length;
        Arrays.sort(nums);
        
        for (int i = 0; i < n - 2; i++) {
            // Skip duplicate first elements
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            
            // Early termination
            if (nums[i] > 0) break;
            
            int left = i + 1;
            int right = n - 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]));
                    
                    // Skip duplicate left values
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    // Skip duplicate right values
                    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 takes O(n log n). The outer loop runs n times, and for each iteration, the two-pointer inner loop runs at most O(n) times (since left and right together traverse the remaining subarray once). Total: O(n log n) + O(n × n) = O(n²). This is a significant improvement over the O(n³) brute force.

Space Complexity: O(1) auxiliary space (excluding the output)

The sorting is done in-place (most implementations use O(log n) stack space for the sort). The two pointers and loop variables use constant space. The output list itself can hold up to O(n²) triplets in the worst case, but this is the required output, not auxiliary space.