Three Sum

Given an integer array nums, return all unique triplets [nums[i], nums[j], nums[k]] such that:

i != j, i != k, and j != k
nums[i] + nums[j] + nums[k] == 0

The solution set must not contain duplicate triplets.

Examples


nums = [-1, 0, 1, 2, -1, -4]
output: [[-1, -1, 2], [-1, 0, 1]]
explanation: The triplets `[-1, -1, 2]` and `[-1, 0, 1]` are the only unique combinations that sum to zero.

nums = [1, 2, -2, -1]
output: []
explanation: There are no three numbers in the array that add up to zero.

nums = [-2, 0, 1, 1, -2, -1, 0, 2, -1]
output: [[-2, 0, 2], [-2, 1, 1], [-1, -1, 2], [-1, 0, 1]]
explanation: The array contains four unique triplets that sum to zero.

Our solution processes the input array by first sorting the array and then using a two-pointer approach to find unique triplets that sum to zero. The algorithm iterates through the sorted array and, for each element nums[i], it sets two pointers: one starting right after i (left = i + 1) and one at the end of the array (right = nums.length - 1).

We calculate the sum of the current element and the two pointers: sum = nums[i] + nums[left] + nums[right].

If the sum is zero, we have found a valid triplet, which we add to the result list.
If the sum is less than zero, we increment the left pointer to increase the sum.
If the sum is greater than zero, we decrement the right pointer to decrease the sum. To avoid processing duplicate triplets, we skip over duplicate elements for both the current element (nums[i]) and the two pointers (left and right).

If the loop completes, we return the list of unique triplets.

The use of sorting ensures that duplicates are easily avoided and the two-pointer approach allows for efficient finding of the triplets.

Check out our lesson on the two-pointer approach to learn more about it and its applications!

from typing import List

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

    for i in range(length - 2):
        # Skip duplicate elements to avoid duplicate triplets
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        left, right = i + 1, length - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total < 0:
                left += 1
            elif total > 0:
                right -= 1
            else:
                result.append([nums[i], nums[left], nums[right]])
                # Skip duplicate elements for left pointer
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                # Skip duplicate elements for right pointer
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                left += 1
                right -= 1

    return result

Time Complexity: The solution has a time complexity of O(n^2), where n is the number of elements in the array. Sorting the array takes O(n log n), and the two-pointer approach iterates over the array in O(n^2) time.

Space Complexity: The solution uses O(1) extra space for the two-pointer technique (excluding the input and output space). Sorting the array is done in-place, so no additional space is required apart from the result storage.

Community solutions

💬 Community guidelines

Stay on topic. Use this section for submitting solutions and providing feedback to others.
Be inclusive. Exponent is a diverse community. Please respect others' opinions and beliefs.

How would you answer? Submit your response below and get feedback from the community.

Anonymous Roadrunner 502

Updated October 6, 2024

Python

from typing import List

def three_sum(nums: List[int]) -> List[List[int]]:
    nums.sort()
    triplets = set()

    for i in range(len(nums) - 2):
        firstNum = nums[i]
        l = i + 1
        r = len(nums) - 1

        while l < r:
            secondNum = nums[l]
            thirdNum = nums[r]

            potentialSum = firstNum + secondNum + thirdNum

            if potentialSum > 0:
                r -= 1
            elif potentialSum < 0:
                l += 1
            else:
                triplets.add((firstNum, secondNum, thirdNum))
                l += 1
                r -= 1
    
    return triplets
    
print(three_sum([0, 1, -1]))

Victor O.

Member

335

February 12, 2025

Java

import java.util.*;

class Solution {

    // Time Complexity: O(n^2)
    // Space Complexity: O(n)
    public static List<List<Integer>> threeSum(int[] nums) {
        // Ensure that the array is sorted first
        Arrays.sort(nums);
        
        // Create the results list to return
        List<List<Integer>> results = new ArrayList<>();

        // Iterate over the length of nums
        for (int i = 0; i < nums.length-2; i++) {
            // We will have the first number in the triplet be fixed

            // Check the we are not duplicating a triplet
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            int secondIdx = i + 1;
            int thirdIdx = nums.length - 1;

            while (secondIdx < thirdIdx) {
                int sum = nums[i] + nums[secondIdx] + nums[thirdIdx];
                if (sum == 0) {
                    // Add this triplet to the arraylist
                    results.add(Arrays.asList(nums[i], nums[secondIdx], nums[thirdIdx]));
                    
                    // Advance both pointers while the number at the next index is the same
                    // as what we just processed to avoid duplicates
                    while (secondIdx < thirdIdx && nums[secondIdx] == nums[secondIdx + 1]) {
                        secondIdx++;
                    }

                    while (secondIdx < thirdIdx && nums[thirdIdx] == nums[thirdIdx - 1]) {
                        thirdIdx--;
                    }

                    // Move both pointers simultaneously
                    secondIdx++;
                    thirdIdx--;
                } else if (sum > 0) {
                    // Sum is larger, so move towards smaller numbers
                    thirdIdx--;
                } else {
                    // Sum is too small, so move towards larger numbers
                    secondIdx++;
                }
            }
        }

        return results;
    }

    public static void main(String[] args) {
        // debug your code below
        int[] arr = {-1, 0, 1, 2, -1, -4};
        System.out.println(threeSum(arr));
    }
}

Divya R.804

March 11, 2025

public static List<List<Integer>> threeSum(int[] nums) { Arrays.sort(nums); List<List<Integer>> resList=new ArrayList<>(); for(int i=0; i<nums.length-2; i++) { if(i>0 && nums[i]==nums[i-1]) continue; int j=i+1; int k=nums.length-1; while(j<k) { int sum=(nums[i] + nums[j] + nums[k]); if(sum==0) { List<Integer> list=Arrays.asList(nums[i], nums[j], nums[k]); resList.add(list); j++; k--; while(j<k && nums[j]==nums[j-1]) j++; while(k>j && nums[k]==nums[k+1]) k--; } else if(sum<0) { j++; } else k--; } } return resList; }

Khyati B.

Member

104

March 27, 2025

Python

from typing import List

# 2nd approach : 1st sort the array and then use 2 pointer approach 
def three_sum(nums: List[int]) -> List[List[int]]:
    nums.sort()  # Sort the array to use the two-pointer approach
    n = len(nums)
    triplet = set()  # We make this a set to avoid duplicate triplets

    # Basic idea is to iterate through each element of the list (except last two as they will be covered eventually)
    for i in range(n - 2):
        target = -nums[i]
        left = i + 1
        right = n - 1
        while left < right:
            if nums[left] + nums[right] == target:
                triplet.add((nums[i], nums[left], nums[right]))  # Adding a tuple to avoid duplicates
                right -= 1
                left += 1
            elif nums[left] + nums[right] < target:
                left += 1
            else:
                right -= 1

    return [list(t) for t in triplet]

See community answers

ML Engineer Introduction

ML System Design Questions

Overview

Mock Interviews & Practice Questions

ML Concepts Questions

Overview

Model & Algorithm Fundamentals

Mock Interviews

ML Coding Questions

Overview

Mock Interviews & Practice Questions

Software Engineering Coding Questions

Overview

Fast Track

Time & Space Complexity

Coding Patterns

Arrays

Hash Tables

Searching & Sorting

String Manipulation

Graphs

Trees

Stacks & Queues

Linked Lists

Heaps

Recursion & Backtracking

Dynamic Programming

Behavioral Interviews: A Practical Guide for Engineers

Fast Track (Start Here)

Theory

Tactics

Mock Interviews & Analyses

Practice

ML Engineer Introduction

ML System Design Questions

Overview

Mock Interviews & Practice Questions

ML Concepts Questions

Overview

Model & Algorithm Fundamentals

Mock Interviews

ML Coding Questions

Overview

Mock Interviews & Practice Questions

Software Engineering Coding Questions

Overview

Fast Track

Time & Space Complexity

Coding Patterns

Arrays

Hash Tables

Searching & Sorting

String Manipulation

Graphs

Trees

Stacks & Queues

Linked Lists

Heaps

Recursion & Backtracking

Dynamic Programming

Behavioral Interviews: A Practical Guide for Engineers

Fast Track (Start Here)

Theory

Tactics

Mock Interviews & Analyses

Practice

Examples