Problem

Given an array of integer write an algorithm to find 3 elements that sum to a zero. In short a+b+c = 0.

OR

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

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.

Solution

Video explanation

Here is the video explaining below methods in detail. Please check it out:

Method 1 - Brute Force

Use 3 nested loops and find the 3 elements which sum to 0.

In the naive approach, we can:

  1. run three nested loops, and generate all possible combinations of three indices (i, j, k) in the array where i != j, i != k, and j != k.
  2. For each combination:
    • Check if nums[i] + nums[j] + nums[k] == 0.
    • If true, add the triplet [nums[i], nums[j], nums[k]] to the result list.
  3. To handle duplicate triplets, use a set to ensure you store only unique triplets.

Code

Java
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        List<List<Integer>> ans = new ArrayList<>();
        Set<String> seenKeys = new HashSet<>(); // HashSet of strings to track unique triplets

        // Three nested loops to find all possible triplets
        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); // Sort the triplet
                        String key = triplet.get(0) + "-" + triplet.get(1) + "-" + triplet.get(2);

                        // Check if the key is unique
                        if (!seenKeys.contains(key)) {
                            seenKeys.add(key);
                            ans.add(triplet);
                        }
                    }
                }
            }
        }

        return ans;
    }
}
Python
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        ans = []
        seen_keys = set()  # HashSet of strings to track unique triplets
        
        # Three nested loops to find all possible triplets
        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    if nums[i] + nums[j] + nums[k] == 0:
                        triplet = [nums[i], nums[j], nums[k]]
                        triplet_sorted = sorted(triplet)
                        key = f"{triplet_sorted[0]}-{triplet_sorted[1]}-{triplet_sorted[2]}"
                        
                        # Check if the key is unique
                        if key not in seen_keys:
                            seen_keys.add(key)
                            ans.append(triplet_sorted)
        
        return ans

Complexity

  • ⏰ Time complexity: O(n^3) where n is the size of the input array as we have 3 nested loops.
  • 🧺 Space complexity: O(1)

Method 2 - Use Hashing

We need 3 numbers (a, b, c), such that their sum is equal to 0 (write a + b + c = 0). So, if fix the first element a in the array, then we have to find two numbers (b, c), such that their sum is equal to -a. Now, this problem is very close to Two Sum problem.

So, this is what we can do:

  1. First, we fix one element at a time from the array. Let’s call this fixed element a. For example, let’s consider a = -1.
  2. Now, our task is to find two numbers (b and c) which should sum up to -a. For example, here the required sum should be +1.
    • This problem now reduces to a Two Sum problem, where we have to find two numbers with a target equal to -a.
  3. Next, we create a HashSet to help track which numbers we’ve seen so far as we iterate through the remaining part of the array. This allows us to efficiently find pairs that complete the triplet.
  4. For each element in this remaining array (let’s call it b), we calculate the remaining value (c) needed to reach the required_sum. Specifically:
    • c = required_sum - b.
  5. Finally, check if c is already in the HashSet:
    • If yes, we’ve found a valid triplet [a, b, c].
    • If not, add b to the HashSet and continue iterating.

Code

Java
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Set<List<Integer>> result = new HashSet<>();
        int n = nums.length;

        for (int i = 0; i < n; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            
            int a = nums[i];
            int requiredSum = -a;
            Set<Integer> seen = new HashSet<>();
            
            for (int j = i + 1; j < n; j++) {
                int b = nums[j];
                int c = requiredSum - b;
                
                if (seen.contains(c)) {
                    List<Integer> triplet = Arrays.asList(a, b, c);
                    Collections.sort(triplet);
                    result.add(triplet);
                } else {
                    seen.add(b);
                }
            }
        }

        return new ArrayList<>(result);
    }
}
Python
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        result = set()
        
        for i in range(n):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            
            a = nums[i]
            required_sum = -a
            seen = set()
            
            for j in range(i + 1, n):
                b = nums[j]
                c = required_sum - b
                
                if c in seen:
                    triplet = tuple(sorted([a, b, c]))
                    result.add(triplet)
                else:
                    seen.add(b)
        
        return [list(t) for t in result]

Complexity

  • ⏰ Time complexity: O(n^2) due to nested loops.
  • 🧺 Space complexity: O(n) for storing the numbers in hashset.

Method 3 - Using Sorting and Two Pointer Approach

Remember the Two Sum problem where we used sorting and the two-pointer approach? There, the time complexity was O(n log n) (for sorting) and the space complexity was O(1) by avoiding extra data structures. Here, even if we use a hashmap for solving the 3Sum problem, we can’t do better than O(n^2) in terms of time complexity.

So, why not just sort the array and use the two-pointer approach to save on space? Another bonus of sorting is that it groups all duplicates together, making it easy to skip repeated numbers without using extra data structures. This simplifies the implementation while maintaining efficiency.

Here is the approach:

  1. Sort the array to enable easy identification of duplicates and efficient traversal using pointers.
  2. Fix one element in the array (let’s call it firstNum or a) as the first number of the triplet.
  3. Use two pointers (left and right) in the remaining part of the array to identify the other two values (b and c) that sum up with a to zero.
  4. Skip duplicates for the fixed element (a) and for the two-pointer traversal (b and c) to ensure only unique triplets are added to the result.

Code

Java
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> triplets = new ArrayList<>();

        Arrays.sort(nums);
        for(int i = 0; i < nums.length-2; i++) {
            if(i > 0 && nums[i] == nums[i-1]) {
                continue;
            }

            int firstNum = nums[i];

            int left = i+1, right = nums.length-1;
            while(left < right) {
                int sum = firstNum + nums[left] + nums[right];
                if(sum == 0) {
                    triplets.add(Arrays.asList(firstNum, nums[left], nums[right]));
                    left++;
                    right--;

                    while(left < right && nums[left] == nums[left-1]) {
                        left++;
                    }
                    while(left < right && nums[right] == nums[right+1]) {
                        right--;
                    }
                } else if(sum < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }

        return triplets;
    }
}
Python
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        triplets = []

        nums.sort()
        for i in range(len(nums) - 2):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            
            first_num = nums[i]
            left, right = i + 1, len(nums) - 1
            
            while left < right:
                total_sum = first_num + nums[left] + nums[right]
                if total_sum == 0:
                    triplets.append([first_num, nums[left], nums[right]])
                    left += 1
                    right -= 1

                    while left < right and nums[left] == nums[left - 1]:
                        left += 1
                    while left < right and nums[right] == nums[right + 1]:
                        right -= 1
                elif total_sum < 0:
                    left += 1
                else:
                    right -= 1

Complexity

  • ⏰ Time complexity: O(n^2)
  • 🧺 Space complexity: O(1)