3Sum

Check every triplet (i, j, k) with i < j < k, and throw the sum into a set of sorted tuples so duplicate triplets (like the two -1s in the example) collapse into one entry. It’s correct by exhaustion, but three nested loops over n elements is cubic, and deduping after the fact still means we generated every duplicate before discarding it.

class Solution:
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        n = len(nums)
        result = set()
        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    if nums[i] + nums[j] + nums[k] == 0:
                        result.add(tuple(sorted((nums[i], nums[j], nums[k]))))
        return [list(t) for t in result]

Why it’s slow: fixing i and j still searches for k one element at a time, redoing work that a smarter data structure (or a sorted array) could do in O(1) or O(log n) — cubic time overall.

Sort the array first so identical values sit next to each other — that makes duplicate triplets easy to skip via i > 0 and nums[i] == nums[i - 1]. For each fixed i, solve the remaining “two numbers that sum to -nums[i]” problem in one pass with a hash set, exactly like the original Two Sum’s optimal approach.

class Solution:
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        nums.sort()
        n = len(nums)
        result = set()
        for i in range(n - 2):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            seen = set()
            for j in range(i + 1, n):
                complement = -nums[i] - nums[j]
                if complement in seen:
                    result.add((nums[i], complement, nums[j]))
                seen.add(nums[j])
        return [list(t) for t in result]

Complexity: the outer loop runs n times and the inner hash-set scan is O(n), giving O(n²) time; the seen set (rebuilt per i) and the result set add up to O(n) space. This is a real improvement over brute force, but the sorted order lets us do even better — no hash set required at all.

Sort the array once. Fix nums[i] as before, but instead of a hash set, solve “two numbers in the remainder that sum to -nums[i]” with converging pointers l and r — the same trick as Two Sum II, which works precisely because the subarray is sorted. Duplicates are skipped by comparing each candidate to its neighbor: once nums[i] has been tried, trying the same value again for i can only reproduce triplets we’ve already found.

class Solution:
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        nums.sort()
        n = len(nums)
        result = []
        for i in range(n - 2):
            if nums[i] > 0:
                break
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            l, r = i + 1, n - 1
            while l < r:
                total = nums[i] + nums[l] + nums[r]
                if total < 0:
                    l += 1
                elif total > 0:
                    r -= 1
                else:
                    result.append([nums[i], nums[l], nums[r]])
                    l += 1
                    r -= 1
                    while l < r and nums[l] == nums[l - 1]:
                        l += 1
                    while l < r and nums[r] == nums[r + 1]:
                        r -= 1
        return result

Tracing nums = [-1, 0, 1, 2, -1, -4] sorted to [-4, -1, -1, 0, 1, 2], once i reaches index 1 (nums[i] = -1):

Correctness: sorting makes the two-pointer argument from Two Sum II apply directly to the subarray nums[i+1:] — if the running sum is too small, only moving l right can increase it; if too big, only moving r left can decrease it. The nums[i] == nums[i-1] skip is safe because any triplet starting with a repeated value would already have been produced when i first pointed at that value. Breaking early once nums[i] > 0 is safe too: in a sorted array, three non-negative numbers starting above zero can never sum to zero.

Complexity: the outer loop is O(n), and for each i the two-pointer scan is O(n) → O(n²) time overall (dominated by the nested scan, with sorting’s O(n log n) absorbed into it). No hash set is needed — just a few pointers — so it’s O(1) extra space beyond the sort and the output itself.