3Sum

The 3Sum problem challenges us to find all unique triplets within an integer array that sum up to zero. A naive approach would involve checking every possible combination of three numbers, resulting in a time complexity of O(n^3). However, by first sorting the array, we can significantly optimize this to O(n^2) using a two-pointer technique.

How it Works

First, the input array is sorted. This crucial step allows us to efficiently manage the sum and skip duplicate triplets. We then iterate through the array with a single pointer, `i`, which locks in the first number of our potential triplet.

For each `nums[i]`, we need to find two other numbers in the remaining part of the array that sum to `-nums[i]`. We achieve this using two additional pointers: `l` (left) and `r` (right). The `l` pointer starts at `i + 1`, and the `r` pointer starts at the end of the array (`len(nums) - 1`).

Inside the `while l < r` loop, we calculate the sum `nums[i] + nums[l] + nums[r]`:

• If the sum is less than zero, it means we need a larger sum. We achieve this by incrementing the `l` pointer, moving it to a potentially larger number.
• If the sum is greater than zero, we need a smaller sum. We achieve this by decrementing the `r` pointer, moving it to a potentially smaller number.
• If the sum is exactly zero, we've found a valid triplet! We add it to our results. To find other unique triplets, we then increment `l` and decrement `r`. Crucially, we also skip any duplicate values at `l` and `r` to ensure uniqueness in our results.

After the inner `while` loop completes for a given `nums[i]`, we advance `i` to the next unique number. This outer loop continues until `i` is two positions away from the end of the array, ensuring there are always at least two elements remaining for `l` and `r`.

def threeSum(nums):
    nums.sort()
    res = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i-1]: continue
        l, r = i + 1, len(nums) - 1
        while l < r:
            s = nums[i] + nums[l] + nums[r]
            if s < 0: l += 1
            elif s > 0: r -= 1
            else:
                res.append([nums[i], nums[l], nums[r]])
                l += 1; r -= 1
                while l < r and nums[l] == nums[l-1]: l += 1
    return res

Key takeaways

• Sorting the array is the first critical step, enabling the two-pointer approach and simplifying duplicate handling.
• The outer loop fixes one element, `nums[i]`, reducing the problem to a two-sum variation.
• Two pointers, `l` and `r`, efficiently search for the remaining two elements in linear time.
• Skipping duplicate elements for `i`, `l`, and `r` is essential to ensure that only unique triplets are added to the result set.
• This approach transforms the problem from O(n^3) to O(n^2) time complexity, dominated by the sorting step and the nested loops.