Two Sum (a+b =s) Problem

By | May 23, 2014

The Two Sum problem is like this :

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

Though this problem looks simple but this problem forms a kind of base for solving other bigger problems like 3sum problem and 4 sum problem . So I advice the users to think on this problem carefully and see what all solutions can be there .

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

We can take different approaches to solve this problem .

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

Approach 2 :
Here’s another way of solving this problem using HashMaps.
Algorithm:

  • Iterate through the array
  • for each element A[i] is the array check if ther’s an element s-A[i] present in the map
  • if yes return A[i] and s-A[i]
  • else add A[i] to map and continue

Here’s the code . It run’s in O(n) time and requires O(n) space .

Approach 3 :
Though the above approach works good . But requires extra space for storing the hash table . Some interviewwers won’t allow you to do that . Here’s another algorithm to solve two sum problem in O(nlgn) without using extra space.
Algorithm

  • Sort the array A
  • Initiale two pointers head =0 and tail= A.length
  • If A[head]+A[Tail]=s return A[head],A[Tail]
  • 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 *