[LeetCode] 15. 3Sum

1. Question

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.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation: 
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

Example 2:

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 
0.

Example 3:

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.

2. Thoughts

There are 4 cases where the sum adds up to 0:
1) 000
2) 0 -x x
3) -z -y z+y
4) -x -x 2x

Make 3 sets- zero, positive, negative
because sets cannot contain duplicates, make a duplicate set
This is because duplicates of 2 or more than 2 are equal (as can see from above)

3. Tips learned

4. My solution

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:

        nums = sorted(nums)
        neg = set()
        pos = set()
        zero = set()
        duplicates = set()
        ans = []

        for num in nums:
            if num == 0:
                if num in zero:
                    if num in duplicates:
                        ans = [[0, 0, 0]]
                    else:
                        duplicates.add(num)
                else:
                    zero.add(num)
            elif num <= 0:
                if num in neg:
                    duplicates.add(num)
                else:
                    neg.add(num)
            else:
                if num in pos:
                    duplicates.add(num)
                else:
                    pos.add(num)

        if zero:
            for num in pos:
                if -num in neg:
                    ans.append(([0, num, -num]))

        used=set()
        for num in pos:
            for second_num in pos:
                if second_num == num or (num,second_num) in used:
                    continue
                else:
                    if -1 * (num + second_num) in neg:
                        ans.append([num, second_num, -(num + second_num)])
                        used.add((second_num,num))

        used=set()
        for num in neg:
            for second_num in neg:
                if second_num == num or (num,second_num) in used:
                    continue
                else:
                    if -1 * (num + second_num) in pos:
                        ans.append([num, second_num, -(num + second_num)])
                        used.add((second_num,num))


        for dup in duplicates:
            if (dup > 0 and dup * -2 in neg) or (dup < 0 and dup * -2 in pos):
                ans.append([dup, dup, dup * -2])

        return ans

189/189 cases passed (989 ms)
Your runtime beats 32.37% of python3 submissions
Your memory usage beats 5.66% of python3 submissions (22.18MB)

5. AI Solution and Improvements

Your approach to solving the 3Sum problem uses sets to track negative numbers, positive numbers, zero occurrences, and duplicates to find triplets that sum to zero. While it's a unique strategy focusing on separating numbers by their sign and handling duplicates carefully, it can be simplified and made more efficient.

A more straightforward and generally faster approach involves sorting the array and using two pointers to find the triplets, drastically reducing the complexity and avoiding the need for multiple sets. This method works well because it allows us to skip over duplicate values and efficiently find two other numbers that, when added to the current number, sum to zero.

Here's how you can implement this method:

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()  # Sort the array to make it easier to skip duplicates
        result = []

        for i in range(len(nums) - 2):
            # Skip duplicate values for the current position
            if i > 0 and nums[i] == nums[i-1]:
                continue

            left, right = i + 1, len(nums) - 1  # Initialize two pointers

            while left < right:
                total = nums[i] + nums[left] + nums[right]

                if total < 0:
                    left += 1  # Move the left pointer to the right
                elif total > 0:
                    right -= 1  # Move the right pointer to the left
                else:
                    # Found a triplet
                    result.append([nums[i], nums[left], nums[right]])
                    left += 1
                    right -= 1

                    # Skip duplicate values for the left and right pointers
                    while left < right and nums[left] == nums[left-1]:
                        left += 1
                    while left < right and nums[right] == nums[right+1]:
                        right -= 1

        return result

This solution works as follows:
1. Sort the array to ensure we can move pointers intelligently based on the sum.
2. Iterate over the array, treating each element as the potential first element of a triplet.
3. Skip Duplicates for the current element to avoid duplicate triplets.
4. Use Two Pointers (left and right) to find two other elements that, combined with the current element, sum to zero.
5. When a zero sum is found, add the triplet to the result and move both pointers, skipping over duplicates for these as well.

This method is efficient, with a time complexity of O(n^2) due to the nested loop (the for loop and the while loop with the two pointers). This is generally the best achievable time complexity for this problem, as you have to examine a significant portion of pairs in the worst case.