Question 15

Three Sum Problem

Given an integer array nums, return all the unique triplets [nums[i], nums[j], nums[k]] such that:

• i != j, i != k, j != k
• nums[i] + nums[j] + nums[k] == 0

---

Approach: Sorting + Two Pointers

Steps:

1. Sort the Array:
   First, sort the input array nums. Sorting helps in two ways:

   • It allows us to skip duplicate values easily.
   • It allows us to use the two-pointer technique to find pairs that sum up to a specific target.

2. Iterate through the Array:
   Loop through each element of the sorted array. For each element at index i, treat it as the first element of the triplet and use the two-pointer technique to find the other two elements.

3. Use Two Pointers:
   For each element nums[i], define two pointers:

   • left starts from the next element (i.e., i + 1).
   • right starts from the end of the array.

   Move the pointers to find two elements whose sum with nums[i] equals zero.

   • If the sum of the three numbers is less than zero, move the left pointer to the right to increase the sum.
   • If the sum is greater than zero, move the right pointer to the left to decrease the sum.
   • If the sum is zero, add the triplet to the result and skip duplicates by moving both pointers.

4. Skip Duplicates:

   • Skip the same values for nums[i], nums[left], and nums[right] to avoid duplicate triplets in the result.

Complexity:

Time Complexity:

• Sorting the array takes (O(nlogn)).
• For each element in the array, we use the two-pointer technique, which takes (O(n)) for each iteration.
• Therefore, the overall time complexity is O(n²).

Space Complexity:

• The space complexity is (O(1)) if we exclude the space required for the result list (which depends on the number of triplets found).

---

Java Code Implementation:

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    if (nums == null || nums.length < 3) {
        return result;
    }

    Arrays.sort(nums);  // Step 1: Sort the array

    for (int i = 0; i < nums.length - 2; i++) {
        // Skip duplicate elements to avoid duplicate triplets
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }

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

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

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

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

                // Move the pointers after finding a valid triplet
                left++;
                right--;
            } else if (sum < 0) {
                left++;
            } else {
                right--;
            }
        }
    }

    return result;
}