Photo by Vishwarajsinh Rana on Unsplash

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.

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

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store