# 3 Sum — Day 38(Python)

Today’s question is another favorite question among FAANG interviewers. Let us look into the problem statement.

15. 3Sum

Given an array `nums` of n integers, are there elements a, b, c in `nums` such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Notice that the solution set must not contain duplicate triplets.

Example 1:

`Input: nums = [-1,0,1,2,-1,-4]Output: [[-1,-1,2],[-1,0,1]]`

Example 2:

`Input: nums = []Output: []`

Example 3:

`Input: nums = [0]Output: []`

Constraints:

One way to solve this problem is to make combinations of three numbers from the given list and check if their addition is equal to 0.

Let us look into the code snippet.

`class ThreeSumFinder:  def threeSum(self, nums: List[int]) -> List[List[int]]:    output = []    for a in range(len(nums)-2):      for b in range(a+1, len(nums)-1):        for c in range(b+1, len(nums)):          if nums[a] + nums[b] + nums[c] == 0:            if sorted([nums[a], nums[b], nums[c]]) not in output:               output.append(sorted([nums[a], nums[b], nums[c]]))    return output`

Complexity

Time Complexity

We are individually trying to find combinations of three numbers. Hence the overall time complexity is O(N³) where N is the number of elements in the list.

Space Complexity

We are not using any extra space, and hence the space complexity will be O(1).

Can we try to improve the time complexity? Can sort before starting the overall algorithm help to find the answer faster?

Let us look into the code snippet.

`class ThreeSumFinder:  def threeSum(self, nums: List[int]) -> List[List[int]]:    nums = sorted(nums)    output = []    for i in range(len(nums)-2):       if i == 0 or i > 0 and nums[i] != nums[i-1]:          low = i + 1          high = len(nums)-1          while(low< high):            if nums[i] + nums[low] + nums[high] == 0:               output.append([nums[i],nums[low],nums[high]])               while(low < high and nums[low] == nums[low+1]):                   low += 1               while(low < high and nums[high] == nums[high-1]):                   high -= 1               low += 1               high -= 1            elif nums[i] + nums[low] + nums[high] < 0:               low +=1            else:               high -= 1    return output`

Complexity

Time Complexity

We are sorting our array which takes O(NlogN). We arerunning a loop to find the first number and within that loop we are running another loop that has pointers pointing to second and third number. The time complexity in the loops section will be O(N²). Hence the overall time complexity for above algorithm is O(N²).

Space Complexity

We are not using any extra space and hence the space complexity will be O(1).

I would like to improve my writing skills, so any suggestions or critiques are highly welcomed.

## More from Annamariya Tharayil

Software Engineer. Find me @ www.linkedin.com/in/annamariya-jt

## Generate Fibonacci Series — The Pythonic way

Get the Medium app