3 Sum

Given an array of integers called nums, find triplets such that [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0

In simpler words, identify three elements in the given array sum such that the sum of these three elements equals to zero. The solution set must not contain duplicate triplets.

Approach

This problem can be solved using the 3 pointer approach. Three pointers namely i, j and k can be used for an optimal output. Among the 3 pointers, 1 will be fixed and 2 will be moving. In each iteration, we will check if the sum i.e. arr[i]+arr[j]+arr[k] is equal to the target i.e. 0.

• If the sum is greater, then we need lesser elements and so we will decrease the value of k (i.e. k–). 
• If the sum is lesser than the target, we need a bigger value and so we will increase the value of j (i.e. j++). 
• If the sum is equal to the target, we will simply insert the triplet i.e. arr[i], arr[j], arr[k], into our answer and move the pointers j and k skipping the duplicate elements.

Algorithm

1. Sort the entire array to make the process of finding triplets easier.
2. Use a loop with a fixed pointer i that iterates from 0 to n-1.
3. Inside the loop, check if the current element is the same as the previous one. If it is, skip to the next iteration to avoid duplicates.
4. Use two moving pointers j (starting from i + 1) and k (starting from the last index).
5. Move j forward and k backward until they cross each other, while keeping i fixed.
6. Check the sum arr[i] + arr[j] + arr[k].
   • If the sum is greater than the target, decrease the value of k.
   • If the sum is lesser than the target, increase the value of j.
   • If the sum is equal to the target, add the triplet (arr[i], arr[j], arr[k]) to the result list and skip duplicate elements while moving pointers j and k.
7. Continue until all unique triplets are found.

Complexity

• Time Complexity: O(NlogN)+O(N2), where N = size of the array.
  • The pointer i, is running for approximately N times. And both the pointers j and k combined can run for approximately N times including the operation of skipping duplicates. So the total time complexity will be O(N2). 

• Space Complexity: O(no. of quadruplets)
  • This space is only used to store the answer. We are not using any extra space to solve this problem. So, from that perspective, space complexity can be written as O(1).

Code

## Java Code

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

public class ThreeSum {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        int n = nums.length;
        Arrays.sort(nums); // Step 1: Sorting the array
        
        for (int i = 0; i < n - 2; i++) { // Step 2: Loop with fixed pointer i
            if (i > 0 && nums[i] == nums[i - 1]) // Avoid duplicates
                continue;
            
            int target = -nums[i]; // Target sum for the remaining two elements
            int j = i + 1; // Two moving pointers
            int k = n - 1;

            while (j < k) { // Two-pointer technique
                int sum = nums[j] + nums[k];

                if (sum == target) { // If sum equals target
                    result.add(Arrays.asList(nums[i], nums[j], nums[k]));
                    j++;
                    k--;

                    while (j < k && nums[j] == nums[j - 1]) j++; // Skip duplicates
                    while (j < k && nums[k] == nums[k + 1]) k--; // Skip duplicates
                } else if (sum < target) { // If sum is lesser than target
                    j++;
                } else { // If sum is greater than target
                    k--;
                }
            }
        }
        
        return result;
    }

    public static void main(String[] args) {
        ThreeSum solution = new ThreeSum();
        int[] nums = {-1, 0, 1, 2, -1, -4};
        List<List<Integer>> result = solution.threeSum(nums);
        System.out.println("Unique triplets that sum up to 0:");
        for (List<Integer> triplet : result) {
            System.out.println(triplet);
        }
    }
}

Output

Unique triplets that sum up to 0:
[-1, -1, 2]
[-1, 0, 1]