Two Pointers: 3Sum

Question:

Write a function threeSum(nums) that takes in an array of integers nums and returns a list of unique triplets [a, b, c] such that a + b + c = 0. The function should return all unique triplets in ascending order.

Example:

print(threeSum([-1, 0, 1, 2, -1, -4]))
# Output: [[-1, -1, 2], [-1, 0, 1]]

print(threeSum([]))
# Output: []

print(threeSum([0]))
# Output: []

Explanation:

To solve this problem, we can use the Two Pointers approach along with sorting the given array.

1. We start by sorting the array in ascending order. Sorting the array will allow us to easily skip over duplicate values and find unique triplets.
2. We initialize an empty list, result, to store the unique triplets that sum up to zero.
3. We iterate over the sorted array, nums, using a loop with index variable i. We iterate until the second-to-last element, as we need at least three elements for a triplet.
4. Inside the loop, we check for duplicate values of nums[i] and skip the current iteration if nums[i] is equal to nums[i-1]. This helps us to avoid duplicate triplets.
   • This check is done by comparing nums[i] with its previous element, nums[i-1]. When i is 0, there is no previous element, so we skip the duplicate check in that case.
5. For each nums[i], we create two pointers, left and right, pointing to the elements on the right side of nums[i]. The left pointer starts from i+1 (next element) and the right pointer starts from the last element of the array.
6. While left is less than right, we enter a loop and perform the following steps:
   • We calculate the sum of nums[i], nums[left], and nums[right].
   • If the sum is equal to 0, we found a valid triplet. We append it to the result list.
   • If the sum is less than 0, it means the sum is smaller than the desired 0, so we move the left pointer one step to the right, increasing the sum.
   • If the sum is greater than 0, it means the sum is larger than the desired 0, so we move the right pointer one step to the left, decreasing the sum.
   • In both cases (moving the left or right pointer), we also skip over any duplicate values by incrementing left until it's greater than its previous index and decrementing right until it's less than its next index.
7. Finally, we return the result list containing all the unique triplets that sum up to zero.

Here's the implementation of the threeSum function in Python:

def threeSum(nums):
    nums.sort()  # Sort the input array in ascending order
    n = len(nums)
    result = []

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

        left = i + 1
        right = n - 1

        while left < right:
            # Calculate the sum of the three elements
            total = nums[i] + nums[left] + nums[right]

            if total == 0:
                result.append([nums[i], nums[left], nums[right]])

                # Skip duplicates
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1

                # Move the pointers
                left += 1
                right -= 1

            elif total < 0:
                left += 1  # Increment left pointer for a smaller sum
            else:
                right -= 1  # Decrement right pointer for a larger sum

    return result

The time complexity of this solution is O(n^2), where n is the length of the nums array. Sorting the array takes O(n log n) time, and the two-pointer approach takes O(n) time.