3 Sum

Given an integer array nums, return all the triplets with sum 0

Two Pointer Approach

Step 1. Sort the array
Step 2. For each index 
    j = i + 1 and k = n - 1
Find the pair which adds to sum 

TC: O(n**2) + O(nlogn)
SC: O(n) ~> Result Array

Solution

def threeSum(self, nums: List[int]):
    res = set()
    nums.sort()
    n = len(nums)
    
    for i in range(n-2):
        j = i+1
        k = n-1
        
        while j < k:
            if nums[i] + nums[j] + nums[k] == 0:
                res.add((nums[i], nums[j], nums[k]))
                j += 1
                k -= 1
            elif nums[i] + nums[j] + nums[k] < 0:
                j += 1
            else:
                k -= 1
                
    return res