15. 3Sum

Intuition

The brute-force way to find all unique triplets that sum to 0 would involve checking all combinations of three numbers, which takes O(n³) time

To do better, we can:

• Sort the array to make it easier to detect and skip duplicates.

• Fix one element and then use a two-pointer approach to find the other two elements whose sum equals the negative of the fixed one.

This brings the time complexity down to O(n²) while avoiding duplicate triplets.

Code

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

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

        // Step 3: Use two pointers to find remaining pair
        int j = i + 1, k = nums.length - 1;
        while (j < k) {
            int sum = nums[i] + nums[j] + nums[k];

            if (sum == 0) {
                triplets.add(Arrays.asList(nums[i], nums[j], nums[k]));
                k--;
                // Step 4: Skip duplicates for third number
                while (k > 0 && nums[k] == nums[k + 1]) k--;
            } else if (sum > 0) {
                k--;
                while (k > 0 && nums[k] == nums[k + 1]) k--; // Skip duplicates
            } else {
                j++;
                while (j < nums.length && nums[j] == nums[j - 1]) j++; // Skip duplicates
            }
        }
    }

    return triplets;
}