27. 3Sum

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. The solution set must not contain duplicate triplets.

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

Input: nums = [0,1,1]
Output: []

Input: nums = [0,0,0]
Output: [[0,0,0]]

Problem Breakdown:

1. Sort the array first. This enables the two-pointer technique and makes it easy to skip duplicates.

• nums.sort()
  result = []

2. Fix one element at index i and use two pointers (left, right) for the remaining subarray. Skip duplicates for the fixed element.

• for i in range(len(nums) - 2):
      if i > 0 and nums[i] == nums[i-1]:
          continue
      left = i + 1
      right = len(nums) - 1

3. Move left and right pointers based on the sum. If sum < 0, move left right. If sum > 0, move right left. If sum == 0, record the triplet.

•     while left < right:
          total = nums[i] + nums[left] + nums[right]
          if total < 0:
              left += 1
          elif total > 0:
              right -= 1
          else:
              result.append([nums[i], nums[left], nums[right]])

4. After finding a triplet, skip duplicate values for both left and right pointers to avoid duplicate triplets.

•             while left < right and nums[left] == nums[left+1]:
                  left += 1
              while left < right and nums[right] == nums[right-1]:
                  right -= 1
              left += 1
              right -= 1

5. Return all unique triplets found.

• return result

Summary:

Sort the array, then for each element use two pointers on the remaining subarray to find pairs that sum to the negative of the fixed element. Skip duplicates at every level to ensure unique triplets.

Time and Space Complexity:

Time Complexity: O(n^2) - sorting is O(n log n), the two-pointer scan for each element is O(n).

Space Complexity: O(1) - excluding the output array, we use constant extra space (sorting may use O(log n)).

Python Solution:

def threeSum(nums):
    nums.sort()
    result = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i-1]:
            continue
        left, right = i + 1, len(nums) - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total < 0:
                left += 1
            elif total > 0:
                right -= 1
            else:
                result.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left] == nums[left+1]:
                    left += 1
                while left < right and nums[right] == nums[right-1]:
                    right -= 1
                left += 1
                right -= 1
    return result

JavaScript Solution:

var threeSum = function(nums) {
    nums.sort((a, b) => a - b);
    const result = [];
    for (let i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] === nums[i-1]) continue;
        let left = i + 1, right = nums.length - 1;
        while (left < right) {
            const total = nums[i] + nums[left] + nums[right];
            if (total < 0) left++;
            else if (total > 0) right--;
            else {
                result.push([nums[i], nums[left], nums[right]]);
                while (left < right && nums[left] === nums[left+1]) left++;
                while (left < right && nums[right] === nums[right-1]) right--;
                left++;
                right--;
            }
        }
    }
    return result;
};

Java Solution:

class Solution {
    public List> threeSum(int[] nums) {
        Arrays.sort(nums);
        List> result = new ArrayList<>();
        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i-1]) continue;
            int left = i + 1, right = nums.length - 1;
            while (left < right) {
                int total = nums[i] + nums[left] + nums[right];
                if (total < 0) left++;
                else if (total > 0) right--;
                else {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    while (left < right && nums[left] == nums[left+1]) left++;
                    while (left < right && nums[right] == nums[right-1]) right--;
                    left++;
                    right--;
                }
            }
        }
        return result;
    }
}