3Sum

How it works

After sorting the array, we can fix one number and then search for the other two using the two-pointer technique. Sorting helps in two ways:

1. It lets us skip duplicates easily.
2. It ensures that moving the left or right pointer will increase or decrease the sum in a predictable way.

For each fixed number a, we place two pointers:

• l starts just after i,
• r starts at the end.

If the current sum is too large, we move r left to reduce it. If the sum is too small, we move l right to increase it. When the sum is exactly zero, we record the triplet and skip duplicates.

Steps

1. Sort the array to handle duplicates and enable two-pointer logic.
2. Loop through the array using index i:
   • Let a = nums[i].
   • If a > 0, break (all remaining numbers are positive).
   • Skip duplicate values for the first number.
3. Set two pointers:
   • l = i + 1
   • r = len(nums) - 1
4. While l < r:
   • Compute threeSum = a + nums[l] + nums[r].
   • If threeSum > 0, move r left.
   • If threeSum < 0, move l right.
   • If threeSum == 0:
     • Add the triplet to the result.
     • Move both pointers inward.
     • Skip duplicates at the left pointer.
5. Return the list of all valid triplets.

Complexity

• Time complexity: O(n^2)
• Space complexity: O(1), plus the space used by the sorting algorithm.
  • This excludes the space used for the output list.
  • If the output list is included, the space is O(m), which is O(n^2) in the worst case.

Where m is the number of unique triplets and n is the length of the given array.

Things to watch for

Forgetting to Skip Duplicates

A common mistake is not properly skipping duplicate values, which leads to duplicate triplets in the result. After sorting, when you find a valid triplet, you must skip over all identical values for the first element (outer loop) and the left pointer. Failing to do this causes wrong answers on inputs like [-1, -1, 0, 1, 1].

Not Sorting the Array First

The two-pointer approach only works correctly on a sorted array. Without sorting, moving pointers based on sum comparisons does not guarantee you will find all valid triplets. Always sort the input array before applying the two-pointer technique.

Incorrect Early Termination

When the first element nums[i] is positive, all remaining elements are also positive (since the array is sorted), so no triplet can sum to zero. However, incorrectly breaking when nums[i] >= 0 instead of nums[i] > 0 misses cases like [0, 0, 0]. The break condition should be nums[i] > 0, not nums[i] >= 0.

from typing import List

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

        for i, a in enumerate(nums):
            if a > 0:
                break

            if i > 0 and a == nums[i - 1]:
                continue

            l, r = i + 1, len(nums) - 1
            while l < r:
                threeSum = a + nums[l] + nums[r]
                if threeSum > 0:
                    r -= 1
                elif threeSum < 0:
                    l += 1
                else:
                    res.append([a, nums[l], nums[r]])
                    l += 1
                    r -= 1
                    while nums[l] == nums[l - 1] and l < r:
                        l += 1

        return res

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;

        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] > 0) break;
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            int l = i + 1, r = nums.size() - 1;
            while (l < r) {
                int sum = nums[i] + nums[l] + nums[r];
                if (sum > 0) {
                    r--;
                } else if (sum < 0) {
                    l++;
                } else {
                    res.push_back({nums[i], nums[l], nums[r]});
                    l++;
                    r--;
                    while (l < r && nums[l] == nums[l - 1]) {
                        l++;
                    }
                }
            }
        }
        return res;
    }
};