Solutions

# Sort and three pointers. Use set or increment index on same number to avoid duplicate triplets.
# two-pointers

# O(n^2) time, O(1) space
def three_sum(nums: list[int]) -> list[list[int]]:
    nums.sort()
    result = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        left = i + 1
        right = len(nums) - 1
        while left < right:
            current_sum = nums[i] + nums[left] + nums[right]
            if current_sum == 0:
                result.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                left += 1
                right -= 1
            elif current_sum < 0:
                left += 1
            else:
                right -= 1
    return result


# Sort and complement hash map - O(n^2) time, O(n) space
def three_sum_hashmap(nums: list[int]) -> list[list[int]]:
    nums.sort()
    result = []
    
    for i in range(len(nums) - 2):
        # Skip duplicate values for the first number
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        
        # For each starting number, use a hashmap for the two-sum
        seen = set()
        target = -nums[i]
        duplicates = set()
        
        for j in range(i + 1, len(nums)):
            complement = target - nums[j]
            
            if complement in seen and nums[j] not in duplicates:
                result.append([nums[i], complement, nums[j]])
                duplicates.add(nums[j])
            
            seen.add(nums[j])
    
    return result