3Sum Problem

3Sum - LeetCode

Intuition:

The problem is to find all unique triplets in the array that sum up to zero. The intuition is to use a two-pointer approach to efficiently search for pairs that complement the current element, leveraging the fact that the array is sorted.

Approach:

1. Sort the Array:

   • Sorting the array allows us to use the two-pointer technique efficiently.

2. Skip Duplicates:

   • Skip duplicate elements for the first element in the triplet to avoid duplicate results.

3. Two-Pointer Technique:

   • Use two pointers (left and right) to efficiently search for pairs that sum to the target.

4. Early Termination:

   • If the current element is already greater than zero, break out of the loop to improve efficiency.

5. Avoid Duplicate Triplets:

   • Skip duplicates for the second and third elements in the triplet to avoid duplicate results.

6. Add Result to the List:

   • Add the triplet to the result list when a valid triplet is found.

Complexity:

• Time Complexity: O(n^2)

  • The nested loops iterate through the array once. The inner loop (two-pointer approach) has a combined time complexity of O(n) because each pointer can move at most n times.

• Space Complexity: O(1)

  • The space complexity is constant as only a constant amount of extra space is used for variables (ans, target, left, right, sum).

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

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();

        // Sort the array
        Arrays.sort(nums);

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

            int target = -nums[i];
            int left = i + 1;
            int right = nums.length - 1;

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

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

                    // Skip duplicates for the second element
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }

                    // Skip duplicates for the third element
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }

                    left++;
                    right--;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }

        return ans;
    }
}