Two Sum Problem

Problem description:

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

Your function should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Solution:

There exist a very obvious quadratic solution, you would just need to loop through the array and for each i element loop from i +1 to n to look for the number which gives you a sum so that array[i] + array[j] = target. This approach works just fine but the problem is that it’s too slow, it runs in quadratic time O(n^2), could we do it better? Yes.

An optimized solution is to use an additional data structure which allows us to keep track of each number that we have and also its index, for this task we could use a HashMap which offers a constant time look-up operation, so we just need to loop the array once to store the elements and their corresponding indices in our HashMap and then loop through the array again and for each element i just check if hashmap.containsKey(target – array[ i ]). Here is the working solution implemented in Java:


public int[] twoSum(int[] numbers, int target) {
        
    HashMap<Integer, Integer> indexes = new HashMap<Integer, Integer>();
        
    for(int i = 0; i < numbers.length; ++i) {
        indexes.put(numbers[i], i);
    }
            
    for(int i = 0; i < numbers.length; ++i) {
        if(indexes.containsKey(target - numbers[i])) {
            return new int[]{i + 1, indexes.get(target - numbers[i]) + 1};
        }
     }
    return null;
}

This solution is much faster than the first approach, this runs in linear time (considering that HashMap look-up operation runs in constant time).

Advertisements

3 thoughts on “Two Sum Problem

  1. Hi, {2, 2, 11, 15}, target 4
    Hashmap will be overriden for this input. How do you handle this?

  2. When adding a number to the hashmap should check if the key is already in . If true you have to check whether the double of the number is equal with the target.

    Also if you have (3,2,4) target 6. You will get 0,0 wich is not correct.

  3. To handle duplicates you need to add elements to hash map dynamically.
    Pseudocode:

    h <- HashMap
    for x in number:
    if target-x in h:
    return indexOf(x)+1, h[target-x]+1
    else:
    h[x] = number.indexOf(x)
    return emptylist

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s