15. 3Sum

https://leetcode.com/problems/3sum/

The problem requires us to find all the set of 3 numbers such that they all add up to 0

Approach 1: Nested Loops

The most naive solution is to try every combination of 3 numbers to see if they add up to zero, and store them in res if they do, else continue looping. In the end, res will have all the numbers that add up to 0 i.e. our answer

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        # https://leetcode.com/problems/3sum/
        res = set()
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                for k in range(j+1, len(nums)):
                    if nums[i] + nums[j] + nums[k] == 0:
                        res.add(tuple(sorted([nums[i], nums[j], nums[k]])))
        return list(map(list, res))

Since we are using three nested loops to iterate over all the combinations, we are going to have a time complexity of n*n*n which will blow up for large arrays, and that is what the leetcode submission results in too (TimeLimitExceeded: passes 311/313 test cases, and fails on the large testcases)

Time Complexity: O(n^3) where n is the length of the array

Space Complexity: O(1)

Approach 2: Target method

The strategy is to basically iterate over the entire array, and basically treat each number as a target for the other numbers to add and cancel out.

We can use linear search to find the target pair of numbers, and to simplify this search we can sort the array first.

To avoid duplicate targets, we will only treat the first copy of every number as a target and if a number equals the one at the previous index, then we can simply continue iterating over the array till we get a new target.

class Solution(object):
    def threeSum(self, nums):
        res = []
        nums.sort()
        length = len(nums)
        for i in range(length-2):
            if nums[i] > 0: 
                break
            if i > 0 and nums[i] == nums[i-1]: 
                continue 

            l, r = i+1, length-1 
            while l < r:
                total = nums[i]+nums[l]+nums[r]

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

We can keep track of 2 indices, l and r if the total = nums[i] + nums[l] + nums[r] is greater than 0 we know we have to reduce our total so reduce the upper bound nums[r] by decrementing r, and if our total is less than 0 we increment the lower bound l

Time Complexity: O(nlogn + n^2) where n is the length of the array

Space Complexity: O(1) [no extra space except res used]