Find All Triplets with Zero Sum

 

Problem Explanation: Find All Triplets with Zero Sum

The task is to find all unique triplets in an array that add up to zero. A triplet consists of three numbers, and the sum of these three numbers should be zero. For example:

Input: [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]

Approach to Solve the Problem

1. Sort the Array:
   First, sort the array in ascending order. Sorting helps to efficiently find the triplets using two pointers.

2. Fix One Element:
   Iterate through the array and fix one element. For each fixed element, find two other elements (using two pointers) such that their sum equals the negative of the fixed element.

3. Use Two Pointers:
   After fixing one element, use two pointers:

   • One pointer starts just after the fixed element.
   • The other pointer starts at the end of the array.
   • Move the pointers closer based on whether the current sum is less than, equal to, or greater than zero.

4. Avoid Duplicates:
   Skip duplicate elements to ensure the triplets are unique.

5. Add Valid Triplets:
   If the sum of the triplet is zero, add it to the result list.

---

Solution Code in Java

import java.util.*;

public class ZeroSumTriplets {

    public static List<List<Integer>> findTriplets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums); // Step 1: Sort the array

        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue; // Skip duplicates for the first element
            }

            int left = i + 1; // Pointer 1
            int right = nums.length - 1; // Pointer 2

            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];

                if (sum == 0) {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));

                    // Move both pointers and skip duplicates
                    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++; // Move the left pointer to increase the sum
                } else {
                    right--; // Move the right pointer to decrease the sum
                }
            }
        }

        return result;
    }

    public static void main(String[] args) {
        int[] nums = {-1, 0, 1, 2, -1, -4};
        List<List<Integer>> triplets = findTriplets(nums);

        System.out.println("Triplets with zero sum: " + triplets);
    }
}

---

Explanation of the Code

1. Sorting: The array is sorted to simplify the two-pointer approach.
2. Outer Loop: Iterates through the array and fixes one element at a time.
3. Inner Logic with Two Pointers:
   • Adjusts pointers based on the sum of the triplet.
   • Adds valid triplets to the result list while skipping duplicates.
4. Output: The program prints all unique triplets with a zero sum.

---

Complexity

• Time Complexity:
  Sorting the array takes $O(n \log n)$, and the two-pointer approach runs in $O(n^2)$, making the overall complexity $O(n^2)$.
• Space Complexity:
  $O(n)$ for storing the result list.

This solution is efficient and easy to implement for finding triplets with zero sum.