3Sum

Problem Statement

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, j != k, and nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets.

Key insights

• “No duplicate triplets” is the hard part — sorting first makes duplicate-skipping easy.
• Fix one number (nums[i]), then reduce to Two Sum II for the rest of the array.
• The two-pointer approach here is the natural extension of Two Sum II to three numbers.

Examples

Input	Output
[-1,0,1,2,-1,-4]	[[-1,-1,2],[-1,0,1]]
[0,1,1]	[]
[0,0,0]	[[0,0,0]]

Constraints

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

Real-World Applications

Where this pattern appears

• Financial reconciliation — find three transactions that cancel each other out (sum to zero).
• Chemical balancing — find three reagents whose net charges sum to neutral.
• 3D vector cancellation — find three force vectors that sum to zero.
• Error detection — find three data values whose sum reveals a specific error pattern.

Complexity Comparison

Approach	Time	Space	Best When
Sort + Two Pointers	O(n²)	O(1)*	Standard answer — elegant and fast
Hash Set	O(n²)	O(n)	Unfamiliar with two-pointer pattern

* O(log n) or O(n) if sorting space counts.

Recommended

Sort + Two Pointers

O(n²) time · O(1) space

Alternative

Hash Set

O(n²) time · O(n) space

Approach 1: Sort + Two Pointers (Recommended)

★ Recommended

Sort the array. For each index i, use two pointers — left = i+1 and right = n-1 — to find pairs that sum to -nums[i]. Skip duplicate values for i and for the inner pointers after finding a triplet.

⏱ Time O(n²) Fixed outer + two-pointer inner 💾 Space O(1) Sorting in-place

Step-by-step Example

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

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

i	nums[i]	left	right	sum	action
0	-4	1→4	5→5	all < 0	left advances to right
1	-1	2	5	-1-1+2=0	✓ add [-1,-1,2], skip dups
1	-1	3	4	-1+0+1=0	✓ add [-1,0,1]
2	-1	skip	—	—	dup of i=1, continue
3	0	4	5	0+1+2=3	>0, right—
3	0	left≥right	—	—	done

Animated walkthrough

Sort + Two Pointers walking through [-1,0,1,2,-1,-4]

Use Next or Autoplay to watch the outer pointer fix one element while inner two pointers converge to find zero-sum triplets.

Back Autoplay Next Reset

Step 1 of 5

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

function threeSum(nums):
    sort(nums)
    result = []
    for i in range(len(nums) - 2):
        if nums[i] > 0: break
        if i > 0 and nums[i] == nums[i-1]: continue  // skip dup outer
        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++
                while left < right and nums[right] == nums[right-1]: right--
                left++; right--
            elif s < 0:
                left++
            else:
                right--
    return result

Solution Code

Python

three_sum_sort_two_pointer.py

from typing import List


def three_sum_sort_two_pointer(nums: List[int]) -> List[List[int]]:
    nums.sort()
    result = []
    n = len(nums)

    for i in range(n - 2):
        if nums[i] > 0:
            break
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        left, right = i + 1, n - 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


print(three_sum_sort_two_pointer([-1, 0, 1, 2, -1, -4]))  # [[-1, -1, 2], [-1, 0, 1]]
print(three_sum_sort_two_pointer([0, 1, 1]))               # []
print(three_sum_sort_two_pointer([0, 0, 0]))               # [[0, 0, 0]]

C++

three_sum_sort_two_pointer.cpp

#include <iostream>
#include <vector>
#include <algorithm>

std::vector<std::vector<int>> threeSumSortTwoPointer(std::vector<int>& nums) {
    std::sort(nums.begin(), nums.end());
    std::vector<std::vector<int>> result;
    int n = (int)nums.size();

    for (int i = 0; i < n - 2; i++) {
        if (nums[i] > 0) break;
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        int left = i + 1, right = n - 1;
        while (left < right) {
            int s = nums[i] + nums[left] + nums[right];
            if (s == 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 (s < 0) {
                left++;
            } else {
                right--;
            }
        }
    }

    return result;
}

int main() {
    std::vector<int> nums = {-1, 0, 1, 2, -1, -4};
    std::vector<std::vector<int>> result = threeSumSortTwoPointer(nums);
    for (const auto& triplet : result) {
        std::cout << "[";
        for (int i = 0; i < (int)triplet.size(); i++) {
            std::cout << triplet[i];
            if (i + 1 < (int)triplet.size()) std::cout << ", ";
        }
        std::cout << "]\n";
    }
    return 0;
}

Java

three_sum_sort_two_pointer.java

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

public class Main {
    public static List<List<Integer>> threeSumSortTwoPointer(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        int n = nums.length;

        for (int i = 0; i < n - 2; i++) {
            if (nums[i] > 0) break;
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int left = i + 1, right = n - 1;
            while (left < right) {
                int s = nums[i] + nums[left] + nums[right];
                if (s == 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 (s < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }

        return result;
    }

    public static void main(String[] args) {
        int[] nums = {-1, 0, 1, 2, -1, -4};
        System.out.println(threeSumSortTwoPointer(nums)); // [[-1, -1, 2], [-1, 0, 1]]
    }
}

JavaScript

three_sum_sort_two_pointer.js

function threeSumSortTwoPointer(nums) {
    nums.sort((a, b) => a - b);
    const result = [];
    const n = nums.length;

    for (let i = 0; i < n - 2; i++) {
        if (nums[i] > 0) break;
        if (i > 0 && nums[i] === nums[i - 1]) continue;
        let left = i + 1, right = n - 1;
        while (left < right) {
            const s = nums[i] + nums[left] + nums[right];
            if (s === 0) {
                result.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 (s < 0) {
                left++;
            } else {
                right--;
            }
        }
    }

    return result;
}

console.log(threeSumSortTwoPointer([-1, 0, 1, 2, -1, -4])); // [[-1,-1,2],[-1,0,1]]
console.log(threeSumSortTwoPointer([0, 1, 1]));               // []
console.log(threeSumSortTwoPointer([0, 0, 0]));               // [[0,0,0]]

Rust

three_sum_sort_two_pointer.rs

fn three_sum_sort_two_pointer(nums: &mut Vec<i32>) -> Vec<Vec<i32>> {
    nums.sort();
    let mut result: Vec<Vec<i32>> = Vec::new();
    let n = nums.len();

    let mut i = 0;
    while i + 2 < n {
        if nums[i] > 0 {
            break;
        }
        if i > 0 && nums[i] == nums[i - 1] {
            i += 1;
            continue;
        }
        let mut left = i + 1;
        let mut right = n - 1;
        while left < right {
            let s = nums[i] + nums[left] + nums[right];
            if s == 0 {
                result.push(vec![nums[i], nums[left], nums[right]]);
                while left < right && nums[left] == nums[left + 1] {
                    left += 1;
                }
                while left < right && nums[right] == nums[right - 1] {
                    right -= 1;
                }
                left += 1;
                right -= 1;
            } else if s < 0 {
                left += 1;
            } else {
                right -= 1;
            }
        }
        i += 1;
    }

    result
}

fn main() {
    let mut nums = vec![-1, 0, 1, 2, -1, -4];
    let result = three_sum_sort_two_pointer(&mut nums);
    println!("{:?}", result); // [[-1, -1, 2], [-1, 0, 1]]
}

Go

three_sum_sort_two_pointer.go

package main

import (
  "fmt"
  "sort"
)

func threeSumSortTwoPointer(nums []int) [][]int {
  sort.Ints(nums)
  result := [][]int{}
  n := len(nums)

  for i := 0; i < n-2; i++ {
    if nums[i] > 0 {
      break
    }
    if i > 0 && nums[i] == nums[i-1] {
      continue
    }
    left, right := i+1, n-1
    for left < right {
      s := nums[i] + nums[left] + nums[right]
      if s == 0 {
        result = append(result, []int{nums[i], nums[left], nums[right]})
        for left < right && nums[left] == nums[left+1] {
          left++
        }
        for left < right && nums[right] == nums[right-1] {
          right--
        }
        left++
        right--
      } else if s < 0 {
        left++
      } else {
        right--
      }
    }
  }

  return result
}

func main() {
  nums := []int{-1, 0, 1, 2, -1, -4}
  result := threeSumSortTwoPointer(nums)
  fmt.Println(result) // [[-1 -1 2] [-1 0 1]]
}

Approach 2: Hash Set

✓ Simple

Sort the array. For each index i, scan j from i+1 to n-1 using a set to check whether -(nums[i] + nums[j]) was already seen in the current inner scan. Because the array is sorted and we skip duplicate i values, sorted triplets are naturally deduplicated.

⏱ Time O(n²) Outer × inner scan 💾 Space O(n) Inner set per outer iteration

Step-by-step Example

Input: [-1, 0, 1, 2, -1, -4] (after sorting: [-4, -1, -1, 0, 1, 2])

For i=1, nums[i]=-1:

• j=2: need = -(-1 + -1) = 2, seen=; 2 not in seen → add -1 to seen
• j=3: need = -(-1 + 0) = 1, seen=-1; 1 not in seen → add 0 to seen
• j=4: need = -(-1 + 1) = 0, seen=0; 0 not in seen → add 1 to seen
• j=5: need = -(-1 + 2) = -1, seen=1; -1 in seen → add [-1,-1,2]

Wait — the triplet is [nums[i], need, nums[j]] = [-1, -1, 2] ✓

Continuing with j=5 already recorded… next i=3, nums[i]=0:

• j=4: need = -(0+1) = -1, seen=; not in seen → add 1
• j=5: need = -(0+2) = -2, seen=1; not in seen → add 2

No new triplets at i=3.

Pseudocode

function threeSumHashSet(nums):
    sort(nums)
    result = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i-1]: continue
        seen = set()
        for j in range(i+1, len(nums)):
            need = -(nums[i] + nums[j])
            if need in seen:
                triplet = [nums[i], need, nums[j]]
                if triplet not in result:
                    result.append(triplet)
            seen.add(nums[j])
    return result

Solution Code

Python

three_sum_hash_set.py

from typing import List


def three_sum_hash_set(nums: List[int]) -> List[List[int]]:
    nums.sort()
    result = []
    n = len(nums)

    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        seen = set()
        j = i + 1
        while j < n:
            need = -(nums[i] + nums[j])
            if need in seen:
                triplet = [nums[i], need, nums[j]]
                if triplet not in result:
                    result.append(triplet)
            seen.add(nums[j])
            j += 1

    return result


print(three_sum_hash_set([-1, 0, 1, 2, -1, -4]))  # [[-1, -1, 2], [-1, 0, 1]]
print(three_sum_hash_set([0, 1, 1]))               # []
print(three_sum_hash_set([0, 0, 0]))               # [[0, 0, 0]]

C++

three_sum_hash_set.cpp

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>

std::vector<std::vector<int>> threeSumHashSet(std::vector<int>& nums) {
    std::sort(nums.begin(), nums.end());
    std::vector<std::vector<int>> result;
    int n = (int)nums.size();

    for (int i = 0; i < n - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        std::unordered_set<int> seen;
        for (int j = i + 1; j < n; j++) {
            int need = -(nums[i] + nums[j]);
            if (seen.count(need)) {
                std::vector<int> triplet = {nums[i], need, nums[j]};
                if (std::find(result.begin(), result.end(), triplet) == result.end()) {
                    result.push_back(triplet);
                }
            }
            seen.insert(nums[j]);
        }
    }

    return result;
}

int main() {
    std::vector<int> nums = {-1, 0, 1, 2, -1, -4};
    std::vector<std::vector<int>> result = threeSumHashSet(nums);
    for (const auto& triplet : result) {
        std::cout << "[";
        for (int i = 0; i < (int)triplet.size(); i++) {
            std::cout << triplet[i];
            if (i + 1 < (int)triplet.size()) std::cout << ", ";
        }
        std::cout << "]\n";
    }
    return 0;
}

Java

three_sum_hash_set.java

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

public class Main {
    public static List<List<Integer>> threeSumHashSet(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        int n = nums.length;

        for (int i = 0; i < n - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            Set<Integer> seen = new HashSet<>();
            for (int j = i + 1; j < n; j++) {
                int need = -(nums[i] + nums[j]);
                if (seen.contains(need)) {
                    List<Integer> triplet = Arrays.asList(nums[i], need, nums[j]);
                    if (!result.contains(triplet)) {
                        result.add(triplet);
                    }
                }
                seen.add(nums[j]);
            }
        }

        return result;
    }

    public static void main(String[] args) {
        int[] nums = {-1, 0, 1, 2, -1, -4};
        System.out.println(threeSumHashSet(nums)); // [[-1, -1, 2], [-1, 0, 1]]
    }
}

JavaScript

three_sum_hash_set.js

function threeSumHashSet(nums) {
    nums.sort((a, b) => a - b);
    const result = [];
    const n = nums.length;

    for (let i = 0; i < n - 2; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) continue;
        const seen = new Set();
        for (let j = i + 1; j < n; j++) {
            const need = -(nums[i] + nums[j]);
            if (seen.has(need)) {
                const triplet = [nums[i], need, nums[j]];
                const key = triplet.join(',');
                if (!result.some(t => t.join(',') === key)) {
                    result.push(triplet);
                }
            }
            seen.add(nums[j]);
        }
    }

    return result;
}

console.log(threeSumHashSet([-1, 0, 1, 2, -1, -4])); // [[-1,-1,2],[-1,0,1]]
console.log(threeSumHashSet([0, 1, 1]));               // []
console.log(threeSumHashSet([0, 0, 0]));               // [[0,0,0]]

Rust

three_sum_hash_set.rs

use std::collections::HashSet;

fn three_sum_hash_set(nums: &mut Vec<i32>) -> Vec<Vec<i32>> {
    nums.sort();
    let mut result: Vec<Vec<i32>> = Vec::new();
    let n = nums.len();

    for i in 0..n.saturating_sub(2) {
        if i > 0 && nums[i] == nums[i - 1] {
            continue;
        }
        let mut seen: HashSet<i32> = HashSet::new();
        for j in (i + 1)..n {
            let need = -(nums[i] + nums[j]);
            if seen.contains(&need) {
                let triplet = vec![nums[i], need, nums[j]];
                if !result.contains(&triplet) {
                    result.push(triplet);
                }
            }
            seen.insert(nums[j]);
        }
    }

    result
}

fn main() {
    let mut nums = vec![-1, 0, 1, 2, -1, -4];
    let result = three_sum_hash_set(&mut nums);
    println!("{:?}", result); // [[-1, -1, 2], [-1, 0, 1]]
}

Go

three_sum_hash_set.go

package main

import (
  "fmt"
  "sort"
)

func threeSumHashSet(nums []int) [][]int {
  sort.Ints(nums)
  result := [][]int{}
  n := len(nums)

  for i := 0; i < n-2; i++ {
    if i > 0 && nums[i] == nums[i-1] {
      continue
    }
    seen := make(map[int]bool)
    for j := i + 1; j < n; j++ {
      need := -(nums[i] + nums[j])
      if seen[need] {
        triplet := []int{nums[i], need, nums[j]}
        duplicate := false
        for _, existing := range result {
          if existing[0] == triplet[0] && existing[1] == triplet[1] && existing[2] == triplet[2] {
            duplicate = true
            break
          }
        }
        if !duplicate {
          result = append(result, triplet)
        }
      }
      seen[nums[j]] = true
    }
  }

  return result
}

func main() {
  nums := []int{-1, 0, 1, 2, -1, -4}
  result := threeSumHashSet(nums)
  fmt.Println(result) // [[-1 -1 2] [-1 0 1]]
}

Approach 3: Optimized Two-Pointer

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

3sum_optimized.py

"""
Solution for 3Sum
"""

def solve():
    """Implementation for approach 3 of 3Sum"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

3sum_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for 3Sum
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

3sumOptimized.java

/**
 * Solution for 3Sum
 * Approach 3
 */
public class 3sumOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

3sum_optimized.js

/**
 * Solution for 3Sum
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

3sum_optimized.rs

/// Solution for 3Sum
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

3sum_optimized.go

package main

import "fmt"

// Solution for 3Sum
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Common Mistakes

Watch for these pitfalls

• Not skipping duplicates for the outer loop: if i > 0 and nums[i] == nums[i-1]: continue
• Not skipping duplicates for left/right pointers after finding a valid triplet
• Applying if nums[i] > 0: break too aggressively or not at all — it only works after sorting
• Forgetting to sort first — without sorting, neither duplicate-skipping nor early termination works

Related Problems

• Two Sum ↗ Easy #1
• Two Sum II ↗ Medium #167
• 4Sum ↗ Medium #18
• Container With Most Water ↗ Medium #11

Interview Tips

Key points to discuss

• Frame it as “fix one + Two Sum II” — interviewers love this framing because it shows systematic problem decomposition.
• The duplicate-skipping logic is the trip wire — walk through it carefully; most candidates forget one of the three skip conditions.
• Time complexity is O(n²) and that is optimal — no known algorithm does better for 3Sum.
• The if nums[i] > 0: break optimization — after sorting, if the smallest remaining number is positive, no triplet can sum to zero.
• Follow-up — 4Sum (#18)? Add one more outer loop and reduce to 3Sum. The pattern generalizes to k-Sum recursively.

← Previous
#11 Container With Most Water Next
#17 Letter Combinations of a Phone Number →