3Sum

Difficulty: Medium

Problem

From the integer array nums, find every group of three entries, taken from three different positions i, j and k, whose values add up to 0. Return each such triplet [nums[i], nums[j], nums[k]], without listing the same combination of values twice.

Example

Input: nums = [-2, 0, 0, 2, 2, -1, 1]
Output: [[-2, 0, 2], [-1, 0, 1]]
Explanation: Only two distinct value combinations reach 0: -2 + 0 + 2 and -1 + 0 + 1. The duplicate 0s and 2s do not create extra triplets.

Brute-force approach

Check every combination of three elements using three nested loops.

Steps

  1. Three nested loops: i, j, k
  2. Check if nums[i] + nums[j] + nums[k] = 0
  3. Store unique triplets
  4. Handle duplicates with a Set

Time complexity: O(n³) · Space complexity: O(k)

Trade-offs

  • Three nested loops is very slow O(n³)
  • Need extra Set to handle duplicates
  • Not suitable for interviews or large inputs

Optimal approach

Key insight: Sort first, then for each fixed element, solve 2Sum with two pointers. Skip duplicates to avoid repeated triplets.

Sort array, fix one element, use two pointers for remaining two.

Steps

  1. Sort the array
  2. Fix first element at index i
  3. Use left = i+1, right = n-1 pointers
  4. If sum < 0, move left right. If sum > 0, move right left
  5. Skip duplicate values to avoid duplicate triplets

Time complexity: O(n²) · Space complexity: O(1)

Pseudocode

function threeSum(nums):
    sort nums
    result = []
    
    for i from 0 to n-2:
        if i > 0 and nums[i] == nums[i-1]:
            continue  // skip duplicates
        
        left = i + 1
        right = n - 1
        
        while left < right:
            sum = nums[i] + nums[left] + nums[right]
            
            if sum == 0:
                add [nums[i], nums[left], nums[right]] to result
                left++, right--
                skip duplicates for left and right
            else if sum < 0:
                left++
            else:
                right--
    
    return result

Hints

  • Sort the array first
  • Fix one element, then use two pointers for the other two
  • Handle duplicates carefully

Complexity questions

Time for three nested loops?

O(n³). Three nested loops = O(n³)

Time with sort + two pointers?

O(n²). O(n log n) sort + O(n) outer × O(n) two pointers = O(n²)

Why do we sort the array first?

Enables two pointers and easy duplicate skipping. Sorting enables two pointers to work and makes skipping duplicates easy

Space complexity (excluding output)?

O(1). O(1) extra space (or O(log n) for sorting stack)

Check your understanding of 3Sum

What does 3Sum ask for?

Three numbers that sum to zero. Find all unique triplets that sum to zero.

Given [-1, 0, 1, 2, -1, -4], what triplets sum to 0?

[[-1, -1, 2], [-1, 0, 1]]. -1 + -1 + 2 = 0 and -1 + 0 + 1 = 0

Why do we need to handle duplicates?

The problem asks for unique triplets only. We need to avoid returning the same triplet multiple times.

Related problems

Keep practising