3 sum problem or a+b+c=sum

By | May 24, 2014

The 3 Sum 🙂 problem is like this :

Given an array of integers A, find 3 numbers a,b,c such that they add up to a specific target number s.
a+b+c =s

The problem is somewhat similar to the two sum problem
.

Ex Input : A={4,5,1,2,3} s=8
output :5,2,1

We can take different approaches to solve this problem .

Here’s the Naive Approach using three for loops trying all possible sums of 3 numbers .The complexity of this solution is O(n^3).

Approach 2:
Here’s a better algorithm to solve 3 sum problem in O(n^2) without using extra space.
If you want to try it before looking at the solution .I’ll give you on hint .

a+b+c=s can be rearranged as a+b=s-c

.
Algorithm

  • Sort the array A
  • for each i in the array Initiale two pointers head =i+1 and tail= A.length
  • If A[head]+A[Tail]=s-A[i] return A[head],A[Tail],A[i]
  • else if A[head]+A[Tail]>s set tail tail= tail-1
  • else if A[head]+A[Tail]>s set tail head= head+1
  • repeat till head <= tail

Here’s the code :

For more interesting questions see our DS/Algo page

Leave a Reply

Your email address will not be published. Required fields are marked *