15. 3Sum - Solution & Explanation

Q: Is 3Sum easy or hard?

3Sum is generally classified as a medium-level problem. The logic becomes manageable once you recognize that sorting allows a two-pointer search, but handling duplicates and avoiding repeated triplets requires careful pointer movement.

Q: How to solve 3Sum in O(n)?

An O(n) solution for the general 3Sum problem is not possible because at least two nested scans are required to examine combinations of three elements. The best known solution is O(n^2) using sorting and the two-pointer technique, which significantly improves over the O(n^3) brute force approach.

Q: What is the best approach for 3Sum?

The most efficient and commonly expected solution uses sorting followed by the two-pointer technique. After sorting the array, fix one element and search for the remaining two numbers using pointers from both ends. This reduces the problem to O(n^2) time and O(1) extra space while making duplicate removal straightforward.

Q: What data structure is used in 3Sum?

The problem primarily uses arrays along with either a hash set for complement lookup or the two-pointer technique after sorting. The hash-based approach relies on O(1) average-time lookups, while the optimized solution leverages the sorted array structure to move pointers efficiently.

Q: What is the time complexity of 3Sum?

The optimal algorithm runs in O(n^2) time. Sorting takes O(n log n), and then each element is used as a fixed value while two pointers scan the rest of the array in linear time. Since this happens for up to n elements, the overall complexity becomes O(n^2).

Q: 3Sum Python or Java solution approach?

Both Python and Java implementations typically sort the array and apply the two-pointer method. Iterate through the array, fix one number, and move two pointers inward while skipping duplicates. This produces all unique triplets in O(n^2) time.

Q: Is 3Sum asked at Google, Amazon, or Meta interviews?

3Sum and its variations appear frequently in technical interviews at companies like Amazon, Meta, Google, and Microsoft. Interviewers use it to test array manipulation, duplicate handling, sorting strategies, and mastery of the two-pointer pattern.

The problem

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

Notice that the solution set must not contain duplicate triplets.

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].
Notice that the order of the output and the order of the triplets does not matter.

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 <= 3000
-10⁵ <= nums[i] <= 10⁵

Approach overview

Problem Overview: Given an integer array nums, return all unique triplets [a, b, c] such that a + b + c = 0. The challenge is avoiding duplicate triplets while keeping the algorithm efficient for large inputs.

Approach 1: Hashing to Track Complements (O(n^2) time, O(n) space)

Fix one element and reduce the problem to a two-sum search for the remaining values. For each index i, iterate through the rest of the array and maintain a hash set of numbers you've seen. For each element nums[j], compute the required complement target = -nums[i] - nums[j] and check the set with an O(1) lookup. If the complement exists, you found a valid triplet. Sorting each discovered triplet or using a set of tuples prevents duplicates. This approach demonstrates the classic array + hashing pattern but uses extra memory and duplicate handling logic.

Approach 2: Two-Pointer Technique After Sorting (O(n^2) time, O(1) extra space)

Sort the array first, which enables an efficient two-pointer search. Iterate through the array and treat each element as the first number of the triplet. For each index i, initialize two pointers: left = i + 1 and right = n - 1. Compute the sum of nums[i] + nums[left] + nums[right]. If the sum is too small, move left forward; if it's too large, move right backward. When the sum equals zero, record the triplet and skip duplicates by advancing pointers past repeated values. Sorting ensures duplicate detection is simple and guarantees each triplet appears only once. This approach combines sorting with the classic two pointers pattern.

The key insight is that once the array is sorted, the remaining search space can be pruned quickly. Increasing the left pointer always increases the sum, and decreasing the right pointer reduces it. That monotonic behavior makes the search deterministic and avoids checking every pair combination.

Recommended for interviews: The sorted two-pointer approach is the expected solution in most coding interviews. It achieves O(n^2) time with O(1) extra space and demonstrates strong understanding of pointer techniques and duplicate handling. Mentioning the hashing variant shows awareness of alternative strategies, but the two-pointer method is cleaner and easier to reason about under interview constraints.

Approach 1: Two-Pointer Technique after Sorting

This approach involves first sorting the array. With the array sorted, you can iterate through the array with a fixed element and use two pointers to find pairs that sum to the negative of the fixed element, effectively finding triplets. This takes advantage of the sorted order to efficiently eliminate duplicates and explore potential solutions.

Python

def threeSum(nums):
    nums.sort()
    res = []
    for i in range(len(nums)):
        if i > 0 and nums[i] == nums[i-1]:
            continue
        left, right = i + 1, len(nums) - 1
        while left < right:
            sum_val = nums[i] + nums[left] + nums[right]
            if sum_val == 0:
                res.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 sum_val < 0:
                left += 1
            else:
                right -= 1
    return res

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ThreeSum {
    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 (i > 0 && nums[i] == nums[i-1]) continue;
            int left = i + 1, right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    res.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 res;
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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 (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) {
                res.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 res;
}

JavaScript

function threeSum(nums) {
    nums.sort((a, b) => a - b);
    const res = [];
    for (let i = 0; i < nums.length; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) continue;
        let left = i + 1, right = nums.length - 1;
        while (left < right) {
            const sum = nums[i] + nums[left] + nums[right];
            if (sum === 0) {
                res.push([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 res;
}

#include <stdio.h>
#include <stdlib.h>

int cmp(const void *a, const void *b) {
    return *(int*)a - *(int*)b;
}

int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    qsort(nums, numsSize, sizeof(int), cmp);
    int **res = malloc(numsSize * sizeof(int*));
    *returnSize = 0;
    *returnColumnSizes = malloc(numsSize * sizeof(int));

    for (int i = 0; i < numsSize - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        int left = i + 1, right = numsSize - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum < 0) left++;
            else if (sum > 0) right--;
            else {
                res[*returnSize] = malloc(3 * sizeof(int));
                res[*returnSize][0] = nums[i];
                res[*returnSize][1] = nums[left];
                res[*returnSize][2] = nums[right];
                (*returnColumnSizes)[*returnSize] = 3;
                (*returnSize)++;
                while (left < right && nums[left] == nums[left + 1]) left++;
                while (left < right && nums[right] == nums[right - 1]) right--;
                left++;
                right--;
            }
        }
    }
    return res;
}

using System;
using System.Collections.Generic;

public class ThreeSumSolution {
    public IList<IList<int>> ThreeSum(int[] nums) {
        Array.Sort(nums);
        IList<IList<int>> res = new List<IList<int>>();
        for (int i = 0; i < nums.Length; i++) {
            if (i > 0 && nums[i] == nums[i-1]) continue;
            int left = i + 1, right = nums.Length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    res.Add(new List<int>(){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 res;
    }
}

In Python, the solution uses list sorting followed by a loop to process each potential triplet with two pointers. This design retains unique results by checking adjacent duplicates before advancing pointers.

Complexity

Time Complexity: O(n^2), primarily influenced by the iterative check of combinations after sorting.

Space Complexity: O(n) accounting for the storage of results.

Try this approach in the editor

Approach 2: Hashing to Avoid Duplicates

This approach employs a hash set to track previously seen elements during pointer adjustment. This helps guide pointer movement and ensures uniqueness without repetitive triplet computation by leveraging stored hash values.

C++

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    set<vector<int>> res;
    for (int i = 0; i < nums.size(); i++) {
        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) {
                res.insert({nums[i], nums[left], nums[right]});
                left++;
                right--;
            } else if (sum < 0) {
                left++;
            } else {
                right--;
            }
        }
    }
    return vector<vector<int>>(res.begin(), res.end());
}

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

int cmp(const void *a, const void *b) {
    return *(int*)a - *(int*)b;
}

bool* seen = NULL;

void reset_seen(int n) {
    for (int i = 0; i < n; i++) seen[i] = false;
}

int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    qsort(nums, numsSize, sizeof(int), cmp);
    int** res = malloc(numsSize * sizeof(int*));
    *returnSize = 0;
    *returnColumnSizes = malloc(numsSize * sizeof(int));
    seen = calloc(numsSize, sizeof(bool));

    for (int i = 0; i < numsSize - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        int left = i + 1, right = numsSize - 1;
        reset_seen(numsSize);
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) {
                if (!seen[left]) {
                    res[*returnSize] = malloc(3 * sizeof(int));
                    res[*returnSize][0] = nums[i];
                    res[*returnSize][1] = nums[left];
                    res[*returnSize][2] = nums[right];
                    (*returnColumnSizes)[*returnSize] = 3;
                    (*returnSize)++;
                    seen[left] = true;
                }
                left++;
                right--;
            } else if (sum < 0) {
                left++;
            } else {
                right--;
            }
        }
    }
    free(seen);
    return res;
}

This implementation in C++ utilizes a set for storing unique triplets, leveraging their properties to avoid duplicate calculations post-loop completion.

Complexity

Time Complexity: O(n^2), with involvement of additional operations for set insertions.

Space Complexity: O(n) approximating storage in the set for unique tracking.

Try this approach in the editor

Approach 3: Sort + Two Pointers

We notice that the problem does not require us to return the triplet in order, so we might as well sort the array first, which makes it easy to skip duplicate elements.

Next, we enumerate the first element of the triplet nums[i], where 0 leq i \lt n - 2. For each i, we can find j and k satisfying nums[i] + nums[j] + nums[k] = 0 by maintaining two pointers j = i + 1 and k = n - 1. In the enumeration process, we need to skip duplicate elements to avoid duplicate triplets.

The specific judgment logic is as follows:

If i \gt 0 and nums[i] = nums[i - 1], it means that the element currently enumerated is the same as the previous element, we can skip it directly, because it will not produce new results.

If nums[i] \gt 0, it means that the element currently enumerated is greater than 0, so the sum of three numbers must not be equal to 0, and the enumeration ends.

Otherwise, we let the left pointer j = i + 1, and the right pointer k = n - 1. When j \lt k, the loop is executed, and the sum of three numbers x = nums[i] + nums[j] + nums[k] is calculated and compared with 0:

If x \lt 0, it means that nums[j] is too small, we need to move j to the right.
If x \gt 0, it means that nums[k] is too large, we need to move k to the left.
Otherwise, it means that we have found a valid triplet, add it to the answer, move j to the right, move k to the left, and skip all duplicate elements to continue looking for the next valid triplet.

After the enumeration is over, we can get the answer to the triplet.

The time complexity is O(n^2), and the space complexity is O(log n). The n is the length of the array.

TypeScript

function threeSum(nums: number[]): number[][] {
    nums.sort((a, b) => a - b);
    const ans: number[][] = [];
    const n = nums.length;
    for (let i = 0; i < n - 2 && nums[i] <= 0; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) {
            continue;
        }
        let j = i + 1;
        let k = n - 1;
        while (j < k) {
            const x = nums[i] + nums[j] + nums[k];
            if (x < 0) {
                ++j;
            } else if (x > 0) {
                --k;
            } else {
                ans.push([nums[i], nums[j++], nums[k--]]);
                while (j < k && nums[j] === nums[j - 1]) {
                    ++j;
                }
                while (j < k && nums[k] === nums[k + 1]) {
                    --k;
                }
            }
        }
    }
    return ans;
}

func threeSum(nums []int) (ans [][]int) {
	sort.Ints(nums)
	n := len(nums)
	for i := 0; i < n-2 && nums[i] <= 0; i++ {
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		j, k := i+1, n-1
		for j < k {
			x := nums[i] + nums[j] + nums[k]
			if x < 0 {
				j++
			} else if x > 0 {
				k--
			} else {
				ans = append(ans, []int{nums[i], nums[j], nums[k]})
				j, k = j+1, k-1
				for j < k && nums[j] == nums[j-1] {
					j++
				}
				for j < k && nums[k] == nums[k+1] {
					k--
				}
			}
		}
	}
	return
}

Rust

use std::cmp::Ordering;

impl Solution {
    pub fn three_sum(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
        nums.sort();
        let n = nums.len();
        let mut res = vec![];
        let mut i = 0;
        while i < n - 2 && nums[i] <= 0 {
            let mut l = i + 1;
            let mut r = n - 1;
            while l < r {
                match (nums[i] + nums[l] + nums[r]).cmp(&0) {
                    Ordering::Less => {
                        l += 1;
                    }
                    Ordering::Greater => {
                        r -= 1;
                    }
                    Ordering::Equal => {
                        res.push(vec![nums[i], nums[l], nums[r]]);
                        l += 1;
                        r -= 1;
                        while l < n && nums[l] == nums[l - 1] {
                            l += 1;
                        }
                        while r > 0 && nums[r] == nums[r + 1] {
                            r -= 1;
                        }
                    }
                }
            }
            i += 1;
            while i < n - 2 && nums[i] == nums[i - 1] {
                i += 1;
            }
        }
        res
    }
}

Ruby

# @param {Integer[]} nums
# @return {Integer[][]}
def three_sum(nums)
  res = []
  nums.sort!

  for i in 0..(nums.length - 3)
    next if i > 0 && nums[i - 1] == nums[i]
    j = i + 1
    k = nums.length - 1
    while j < k do
      sum = nums[i] + nums[j] + nums[k]
      if sum < 0
        j += 1
      elsif sum > 0
        k -= 1
      else
        res += [[nums[i], nums[j], nums[k]]]
        j += 1
        k -= 1
        j += 1 while nums[j] == nums[j - 1]
        k -= 1 while nums[k] == nums[k + 1]
      end
    end
  end

  res
end

PHP

class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer[][]
     */
    function threeSum($nums) {
        sort($nums);
        $ans = [];
        $n = count($nums);
        for ($i = 0; $i < $n - 2 && $nums[$i] <= 0; ++$i) {
            if ($i > 0 && $nums[$i] == $nums[$i - 1]) {
                continue;
            }
            $j = $i + 1;
            $k = $n - 1;
            while ($j < $k) {
                $x = $nums[$i] + $nums[$j] + $nums[$k];
                if ($x < 0) {
                    ++$j;
                } elseif ($x > 0) {
                    --$k;
                } else {
                    $ans[] = [$nums[$i], $nums[$j++], $nums[$k--]];
                    while ($j < $k && $nums[$j] == $nums[$j - 1]) {
                        ++$j;
                    }
                    while ($j < $k && $nums[$k] == $nums[$k + 1]) {
                        --$k;
                    }
                }
            }
        }
        return $ans;
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Two-Pointer Technique after Sorting	Time Complexity: O(n^2), primarily influenced by the iterative check of combinations after sorting. Space Complexity: O(n) accounting for the storage of results.
Hashing to Avoid Duplicates	Time Complexity: O(n^2), with involvement of additional operations for set insertions. Space Complexity: O(n) approximating storage in the set for unique tracking.
Sort + Two Pointers	–

Approach

Complexity

Two-Pointer Technique after Sorting

Time Complexity: O(n^2), primarily influenced by the iterative check of combinations after sorting.

Space Complexity: O(n) accounting for the storage of results.

Hashing to Avoid Duplicates

Time Complexity: O(n^2), with involvement of additional operations for set insertions.

Space Complexity: O(n) approximating storage in the set for unique tracking.

Sort + Two Pointers

–

Complexity analysis

Approach	Time	Space	When to Use
Hashing with Fixed Element	O(n^2)	O(n)	When you want a direct extension of the Two Sum hash map technique
Sorting + Two Pointers	O(n^2)	O(1) extra	Best general solution; clean duplicate handling and standard interview expectation
Brute Force Triple Loop	O(n^3)	O(1)	Only useful for explaining the baseline before optimization

Frequently asked questions

Is 3Sum easy or hard?

3Sum is generally classified as a medium-level problem. The logic becomes manageable once you recognize that sorting allows a two-pointer search, but handling duplicates and avoiding repeated triplets requires careful pointer movement.

How to solve 3Sum in O(n)?

An O(n) solution for the general 3Sum problem is not possible because at least two nested scans are required to examine combinations of three elements. The best known solution is O(n^2) using sorting and the two-pointer technique, which significantly improves over the O(n^3) brute force approach.

What is the best approach for 3Sum?

The most efficient and commonly expected solution uses sorting followed by the two-pointer technique. After sorting the array, fix one element and search for the remaining two numbers using pointers from both ends. This reduces the problem to O(n^2) time and O(1) extra space while making duplicate removal straightforward.

What data structure is used in 3Sum?

The problem primarily uses arrays along with either a hash set for complement lookup or the two-pointer technique after sorting. The hash-based approach relies on O(1) average-time lookups, while the optimized solution leverages the sorted array structure to move pointers efficiently.

What is the time complexity of 3Sum?

The optimal algorithm runs in O(n^2) time. Sorting takes O(n log n), and then each element is used as a fixed value while two pointers scan the rest of the array in linear time. Since this happens for up to n elements, the overall complexity becomes O(n^2).

3Sum Python or Java solution approach?

Both Python and Java implementations typically sort the array and apply the two-pointer method. Iterate through the array, fix one number, and move two pointers inward while skipping duplicates. This produces all unique triplets in O(n^2) time.

Is 3Sum asked at Google, Amazon, or Meta interviews?

3Sum and its variations appear frequently in technical interviews at companies like Amazon, Meta, Google, and Microsoft. Interviewers use it to test array manipulation, duplicate handling, sorting strategies, and mastery of the two-pointer pattern.

3Sum solution and explanation

The problem

Approach overview

Approach 1: Two-Pointer Technique after Sorting

Approach 2: Hashing to Avoid Duplicates

Approach 3: Sort + Two Pointers

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

3Sum solution and explanation

The problem

Approach overview

Approach 1: Two-Pointer Technique after Sorting

Approach 2: Hashing to Avoid Duplicates

Approach 3: Sort + Two Pointers

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems