# 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:**

`0 <= nums.length <= 3000`

`-105 <= nums[i] <= 105`

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?

- Sort the array.
- Run a loop to get the first number. The current number should be different from the previous number. This helps in avoiding duplicate answers.
- Start from the number next to the first number, this will be our second number. The third number will be from the end of the loop.
- If the addition of all three numbers results in 0, we have found a solution. Insert the values of all three numbers in the output list. Increment the pointer value of the second number, and decrement the pointer value of the third number. Ensure we avoid repeating the same numbers while incrementing/decrementing the pointer values.
- If the sum of all three numbers results in a value lesser than 0, then increment the pointer value of the second number.
- If the sum of all three numbers results in a value greater than 0, then decrement the pointer value of the third number.

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.