Image for post
Image for post
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:

Example 2:

Example 3:

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.

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?

  1. Sort the array.
  2. Run a loop to get the first number. The current number should be different from the previous number. This helps in avoiding duplicate answers.
  3. 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.
  4. 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.
  5. If the sum of all three numbers results in a value lesser than 0, then increment the pointer value of the second number.
  6. 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.

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