3Sum — Solution in C++, Java, Python, Go

Q: What is the optimal time complexity of 3Sum?

The most efficient approach in this guide ("Sort + Two Pointers") runs in O(n^2) time and uses O(1) excluding the output array extra space. Earlier brute-force approaches are slower; see all 2 approaches above for the full progression.

Q: What pattern does 3Sum use?

3Sum is a medium-level Two Pointers problem involving Array, Two Pointers, Sorting. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Q: Can 3Sum be solved without extra space?

The most space-efficient approach in this guide uses O(1) excluding the output array extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(1) excluding the output array, while the optimized version uses O(1) excluding the output array.

Q: Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

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. Find all unique triplets in the array that sum to zero without returning duplicate triplets.

Notice that the solution set must not contain duplicate triplets. The order of the output and the order of the triplets does not matter.

Examples

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].

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^5 <= nums[i] <= 10^5

Approaches

2 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Brute Force

Intuition

The most direct approach is to check every possible combination of three elements. We use three nested loops to generate all triplets and check if they sum to zero. To avoid duplicates we can sort the array first and skip elements that are the same as the previous one at each loop level. While simple to understand, the cubic time complexity makes this approach too slow for large inputs.

Algorithm

Sort the input array in ascending order.
Use three nested loops to iterate through all combinations of indices i < j < k.
For each combination, check if nums[i] + nums[j] + nums[k] equals 0.
Skip duplicate values at each level to avoid duplicate triplets.
If the sum is zero, add the triplet to the result list.

TimeO(n^3)SpaceO(1) excluding the output array

Code (C++ · Java · Python · Go)

C++17

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        int n = nums.size();

        for (int i = 0; i < n - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            for (int j = i + 1; j < n - 1; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                for (int k = j + 1; k < n; k++) {
                    if (k > j + 1 && nums[k] == nums[k - 1]) continue;
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        result.push_back({nums[i], nums[j], nums[k]});
                    }
                }
            }
        }

        return result;
    }
};

Java 21

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

        for (int i = 0; i < n - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            for (int j = i + 1; j < n - 1; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                for (int k = j + 1; k < n; k++) {
                    if (k > j + 1 && nums[k] == nums[k - 1]) continue;
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        result.add(Arrays.asList(nums[i], nums[j], nums[k]));
                    }
                }
            }
        }

        return result;
    }
}

Python 3.12

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

    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        for j in range(i + 1, n - 1):
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue
            for k in range(j + 1, n):
                if k > j + 1 and nums[k] == nums[k - 1]:
                    continue
                if nums[i] + nums[j] + nums[k] == 0:
                    result.append([nums[i], nums[j], nums[k]])

    return result

Go 1.26

import "sort"

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

    for i := 0; i < n-2; i++ {
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }
        for j := i + 1; j < n-1; j++ {
            if j > i+1 && nums[j] == nums[j-1] {
                continue
            }
            for k := j + 1; k < n; k++ {
                if k > j+1 && nums[k] == nums[k-1] {
                    continue
                }
                if nums[i]+nums[j]+nums[k] == 0 {
                    result = append(result, []int{nums[i], nums[j], nums[k]})
                }
            }
        }
    }

    return result
}

Approach 2

Sort + Two Pointers

Intuition

By sorting the array first, we can reduce the problem to a series of two-sum problems. For each element nums[i], we need to find two numbers in the remaining array that sum to -nums[i]. Since the array is sorted, we can use two pointers starting from both ends of the remaining subarray and move them inward based on the current sum. Skipping duplicate values at each step ensures we produce only unique triplets.

Algorithm

Sort the array in ascending order.
Iterate through each element nums[i] as the first number of the triplet. If nums[i] > 0, break early since no three positive numbers can sum to zero.
Skip duplicate values for i to avoid duplicate triplets.
Set two pointers: left = i + 1 and right = n - 1.
While left < right, compute the sum of nums[i] + nums[left] + nums[right].
If the sum is zero, record the triplet, then advance both pointers while skipping duplicates.
If the sum is less than zero, increment left. If greater than zero, decrement right.

TimeO(n^2)SpaceO(1) excluding the output array

Code (C++ · Java · Python · Go)

C++17

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        int n = 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 sum = nums[i] + nums[left] + nums[right];
                if (sum == 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 (sum < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }

        return result;
    }
};

Java 21

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        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 sum = nums[i] + nums[left] + nums[right];
                if (sum == 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 (sum < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }

        return result;
    }
}

Python 3.12

def threeSum(nums: list[int]) -> list[list[int]]:
    result = []
    nums.sort()
    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:
            total = nums[i] + nums[left] + nums[right]
            if total == 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 total < 0:
                left += 1
            else:
                right -= 1

    return result

Go 1.26

import "sort"

func threeSum(nums []int) [][]int {
    sort.Ints(nums)
    var 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 {
            sum := nums[i] + nums[left] + nums[right]
            if sum == 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 sum < 0 {
                left++
            } else {
                right--
            }
        }
    }

    return result
}

Frequently asked questions

What is the optimal time complexity of 3Sum?

The most efficient approach in this guide ("Sort + Two Pointers") runs in O(n^2) time and uses O(1) excluding the output array extra space. Earlier brute-force approaches are slower; see all 2 approaches above for the full progression.

What pattern does 3Sum use?

3Sum is a medium-level Two Pointers problem involving Array, Two Pointers, Sorting. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can 3Sum be solved without extra space?

The most space-efficient approach in this guide uses O(1) excluding the output array extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(1) excluding the output array, while the optimized version uses O(1) excluding the output array.

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Original problem: leetcode.com

Loading editor...

Input

nums=

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

Expected Output

[[-1,-1,2],[-1,0,1]]