Course4all
Join us on telegram
Home/dsa/Two Pointers/3Sum

3Sum

Master this topic with zero to advance depth.

3Sum

Given an integer array nums, return all the unique triplets [nums[i], nums[j], nums[k]] such that i \neq j, i \neq k, and j \neq k, and nums[i] + nums[j] + nums[k] == 0.

Visual Representation

Sorted Array: [-4, -1, -1, 0, 1, 2] Step 1: Fix i = -1 (Index 1) L = -1 (Index 2), R = 2 (Index 5) Sum = -1 + (-1) + 2 = 0 -> FOUND! [-1, -1, 2] Step 2: L moves to 0 (Index 3), R moves to 1 (Index 4) Sum = -1 + 0 + 1 = 0 -> FOUND! [-1, 0, 1]
Medium

Examples

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

The triplets are (-1, 0, 1) and (-1, -1, 2).

Approach 1

Level I: Brute Force (Check All Triplets)

Intuition

Check every possible combination of three numbers to see if they sum to zero. To avoid duplicate triplets, we can sort each triplet and store it in a Set.

⏱ O(N^3)💾 O(k) where k is the number of triplets

Detailed Dry Run

| i | j | k | nums[i] | nums[j] | nums[k] | Sum | Result | | :--- | :--- | :--- | :--- | :--- | :--- | :--- | | 0 | 1 | 2 | -1 | 0 | 1 | 0 | FOUND! [-1, 0, 1] |

java
import java.util.*;

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

    public static void main(String[] args) {
        System.out.println(new Solution().threeSum(new int[]{-1, 0, 1, 2, -1, -4}));
    }
}

⚠️ Common Pitfalls & Tips

O(N^3) complexity is too slow for N > 1000.

Approach 2

Level II: Better (Sorting + Binary Search)

Intuition

If we sort the array and fix two elements nums[i] and nums[j], we need to find -(nums[i] + nums[j]) in the remaining part of the array. Since it is sorted, we can use binary search.

  1. Sort the array.
  2. Fix two pointers i and j.
  3. Search for the required third value using binary search in the range (j+1, n-1).
⏱ O(N^2 log N)💾 O(1)

Detailed Dry Run

Input: [-1, 0, 1, 2, -1, -4]. Sorted: [-4, -1, -1, 0, 1, 2]

  1. i=-4, j=-1: Search for 5? Not found.
  2. i=-1, j=-1: Search for 2? FOUND at index 5. Result: [-1, -1, 2].
  3. i=-1, j=0: Search for 1? FOUND at index 4. Result: [-1, 0, 1].
java
public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    Set<List<Integer>> res = new HashSet<>();
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            int target = -(nums[i] + nums[j]);
            int low = j + 1, high = nums.length - 1;
            while (low <= high) {
                int mid = low + (high - low) / 2;
                if (nums[mid] == target) {
                    res.add(Arrays.asList(nums[i], nums[j], nums[mid]));
                    break;
                }
                if (nums[mid] < target) low = mid + 1;
                else high = mid - 1;
            }
        }
    }
    return new ArrayList<>(res);
}

⚠️ Common Pitfalls & Tips

O(N^2 log N) is better than O(N^3) but still not as good as the O(N^2) two-pointer solution.

Approach 3

Level III: Optimal (Sort + Two Pointers)

Intuition

To optimize, we sort the array first. This allows us to use the Two Pointers technique for the 'Two Sum' part of the problem.

  1. Fix the first element nums[i].
  2. Use Two Pointers (L = i+1, R = n-1) to find pairs that sum to -nums[i].
  3. Skip duplicate values for i, L, and R to ensure unique triplets.
⏱ O(N^2)💾 O(1) (excluding sorting space)

Detailed Dry Run

Input: [-1, 0, 1, 2, -1, -4]. Sorted: [-4, -1, -1, 0, 1, 2]

ival[i]LRSumAction
0-41 (-1)5 (2)-3Sum < 0, L++
1-12 (-1)5 (2)0FOUND! L++, R--
1-13 (0)4 (1)0FOUND! L++, R--
java
import java.util.*;

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 - 2; i++) {
            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) {
                    res.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    while (l < r && nums[l] == nums[l + 1]) l++;
                    while (l < r && nums[r] == nums[r - 1]) r--;
                    l++; r--;
                } else if (sum < 0) l++;
                else r--;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(new Solution().threeSum(new int[]{-1, 0, 1, 2, -1, -4}));
    }
}

⚠️ Common Pitfalls & Tips

Remember to skip duplicate values for all three pointers to avoid duplicate triplets in the result.

← Previous QuestionTwo Sum II - Input Array Is Sorted
Next Question →4Sum