3 Sum

05 September 2024 — approx 5 min read.

Given an integer array nums, return all the triplets that sum up to 0. Notice that the solution set must not contain duplicate triplets.

Problem Statement

LeetCode-15: 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.

Approach

The problem is an extension of the 2-sum problem. Another thing to notice is that the solution set must not contain duplicate triplets.

Let’s try to extend the 2-sum approach to solve this problem. We can fix one element and then find the other two elements such that their sum is equal to the negative of the fixed element.

This way, we can reduce the problem to a 2-sum problem.

Also, to ensure that the solution set does not contain duplicate triplets, we can sort the array and skip the duplicate elements while iterating over the array.

Sorting the array gives us another advantage. We can use two pointers to find the other two elements such that their sum is equal to the negative of the fixed element. Here is the approach:

Sort the array.
Iterate over the array while skipping duplicate elements.
Fix one element and find the other two elements (towards the right of fixed element) such that their sum is equal to the negative of the fixed element. In other words, the three elements should sum up to 0.
1. To find the other two elements, use two pointers. One pointer starts from the element next to the fixed element, and the other pointer starts from the end of the array.
2. If the sum of the three elements is equal to 0, add the triplet to the result.
3. If the sum is less than 0, increment the left pointer.
4. If the sum is greater than 0, decrement the right pointer.
5. Skip the duplicate elements while iterating over the array.
Return the result.

Let’s see a working example to understand the approach better.

Implementation

public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    int index = 0;
    List<List<Integer>> result = new ArrayList<>();

    while(index < nums.length){
        if(index == 0 || nums[index] != nums[index-1]){
            int one = nums[index];
            int start = index+1;
            int end = nums.length -1;
    
            while(start < end){
                int two = nums[start];
                int three = nums[end];
                if(one + two + three == 0){
                    result.add(List.of(one, two, three));
                    start++;
                    end--;
                    while(start < end && nums[start] == nums[start-1]){
                        start++;
                    }
                }else if(one + two + three < 0){
                    start++;
                }else{
                    end--;
                }
            }
        }
        index++;
    }
    return result;
}

Complexity Analysis

Due to the array sorting and nested loops, the overall time complexity for this approach is $O(n \cdot \log n + n^2) \approx O(n^2)$, where $n$ is the number of elements in the array.

The space complexity is $O(1)$, as we are using only a constant amount of extra space.

Follow-up

Working with a similar method, instead of using two-pointer approach, we can use a HashSet to store the elements and then find the other two elements such that their sum is equal to the negative of the fixed element.

Here is the approach:

public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    int index = 0;
    List<List<Integer>> result = new ArrayList<>();
    
    while(index < nums.length){
        if(index == 0 || nums[index] != nums[index-1]){
            Set<Integer> uniq = new HashSet<>();
            for(int i=index+1; i < nums.length; i++){
                int one = nums[index];
                int two = nums[i];
                int compliment = -one-two;
                
                if(uniq.contains(compliment)){
                    result.add(List.of(one, two, compliment));
                    while(i < nums.length-1 && nums[i] == nums[i+1]){
                        i++;
                    }
                }
                uniq.add(two);
            }
        
        }
        index++;
    }
    return result;
}

As it is with the previous approach, the overall time complexity for this approach is still $O(n \cdot \log n + n^2) \approx O(n^2)$, where $n$ is the number of elements in the array. Additionally, the space complexity is $O(n)$, as we are using a HashSet to store the elements.

But, is there a way to solve this problem in just $O(n^2)$ time that avoids the additional complexity of sorting the array?

Here is the approach:

public List<List<Integer>> threeSum(int[] nums) {
        Set<Integer> uniq = new HashSet<>();
        Set<List<Integer>> result = new HashSet<>();

        int index = 0;

        while(index < nums.length){
            int one = nums[index];

            // re-create hashmap or clear if created outside
            // to ensure the map is reset in every iteration
            // this ensures that compliment's presence is not
            // checked across the iterations
            Map<Integer, Integer> mapping = new HashMap<>();

            // if not seen before
            // add to the set
            if(uniq.add(one)){
                for(int i = index+1; i < nums.length; i++){
                    int two = nums[i];
                    int compliment = -one-two;

                    // if the map is NOT cleared 
                    // and is created outside of while loop
                    // the add a check on index as well
                    // mapping.containsKey(compliment) && mapping.get(compliment) == index
                    if(mapping.containsKey(compliment)){
                        List<Integer> temp = Arrays.asList(one, two, compliment);
                        Collections.sort(temp);
                        result.add(temp);
                    }

                    mapping.put(two, index);
                }
            }

            index++;
        }

        return new ArrayList<>(result);
    }

The above approach uses a HashSet to store the unique elements and a HashMap to store the elements and their indices. This way, we can avoid the additional complexity of sorting the array.

The overall time complexity for this approach is $O(n^2)$, where $n$ is the number of elements in the array. The space complexity is $O(n)$, as we are using a HashSet and a HashMap to store the elements.

@dsadaily