3Sum - Java Solution

1. Introduction

This blog post delves into solving the classic "3Sum" problem, a staple in algorithmic interviews. The challenge involves finding all unique triplets in an array that add up to zero. It's a problem that tests our ability to use array sorting and two-pointer techniques effectively.

Problem

We are given an integer array 'nums'. Our task is to find all unique triplets in the array [nums[i], nums[j], nums[k]] such that i, j, and k are distinct indices, and their sum equals zero. It's crucial to ensure that the solution set does not contain any duplicate triplets.

2. Solution Steps

1. Sort the array to simplify finding triplets and avoiding duplicates.

2. Iterate through the array, taking each element as a potential first element of a triplet.

3. For each element, use two pointers to find pairs that sum up to the negative of that element.

4. Skip over duplicate elements to avoid duplicate triplets.

5. Store all unique triplets that meet the criteria.

3. Code Program

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

public class ThreeSum {
    public static void main(String[] args) {
        int[] nums = {-1, 0, 1, 2, -1, -4};
        List<List<Integer>> triplets = threeSum(nums);
        System.out.println(triplets); // Display the triplets
    }

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

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

                while (low < high) {
                    if (nums[low] + nums[high] == sum) {
                        result.add(Arrays.asList(nums[i], nums[low], nums[high]));
                        while (low < high && nums[low] == nums[low + 1]) low++; // Skip duplicates
                        while (low < high && nums[high] == nums[high - 1]) high--; // Skip duplicates
                        low++;
                        high--;
                    } else if (nums[low] + nums[high] < sum) {
                        low++;
                    } else {
                        high--;
                    }
                }
            }
        }
        return result;
    }
}

Output:

[[-1, -1, 2], [-1, 0, 1]]

Explanation:

1. threeSum: This function first sorts the array to simplify the process of finding triplets and avoiding duplicates.

2. It iterates through the array, treating each element as a potential first element of a triplet.

3. For each element, it uses a two-pointer approach to find pairs whose sum equals the negative of the current element.

4. The function skips duplicate elements to ensure that the result set contains only unique triplets.

5. It adds qualifying triplets to the result list and continues until all possibilities are exhausted.

6. The final result is a list of all unique triplets in the array that sum up to zero.