Find All Triplets With Zero Sum - Java Solution

1. Introduction

This blog post is dedicated to solving a classic problem in array processing: finding all triplets in an array that sum up to zero. This problem is a great example of using a combination of sorting and two-pointer techniques.

Problem

Given an array of integers, the task is to find all unique triplets in the array which sum up to zero.

Example:

Input: nums = [-1, 0, 1, 2, -1, -4]

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

Explanation: The triplets with a sum of zero are [-1, -1, 2] and [-1, 0, 1].

2. Solution Steps

1. Sort the array.

2. Iterate through the array, taking one number at a time.

3. Use two pointers to find other two numbers which make the sum zero.

4. Skip duplicated elements to avoid duplicate triplets.

5. Store all unique triplets that sum up to zero.

3. Code Program

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

public class Solution {

    // Main method for testing
    public static void main(String[] args) {
        int[] nums = {-1, 0, 1, 2, -1, -4};
        System.out.println("Triplets with zero sum: " + threeSum(nums));
    }

    // Method to find all unique triplets that sum up to zero
    public static List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> triplets = new ArrayList<>();

        for (int i = 0; i < nums.length - 2; i++) {
            // Skip duplicate elements
            if (i == 0 || (i > 0 && nums[i] != nums[i - 1])) {
                int low = i + 1, high = nums.length - 1, sum = 0 - nums[i];

                while (low < high) {
                    if (nums[low] + nums[high] == sum) {
                        triplets.add(Arrays.asList(nums[i], nums[low], nums[high]));

                        // Skip duplicate elements
                        while (low < high && nums[low] == nums[low + 1]) low++;
                        while (low < high && nums[high] == nums[high - 1]) high--;

                        low++; high--;
                    } else if (nums[low] + nums[high] < sum) {
                        low++;
                    } else {
                        high--;
                    }
                }
            }
        }
        return triplets;
    }
}

Output:

Triplets with zero sum: [[-1, -1, 2], [-1, 0, 1]]

Explanation:

The threeSum method first sorts the array and then iterates through it, using two pointers for each element to find the other two elements that sum up to zero. It avoids duplicates by skipping over repeated elements. 

For the input array [-1, 0, 1, 2, -1, -4], the method finds two unique triplets that sum up to zero: [-1, -1, 2] and [-1, 0, 1].