Data Structures in Java: Two Sum Problem

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

Each input should have exactly one solution and you may not use the same element twice.

Example,

arr_nums = [7, 4, 2, 11, 20], target = 6

Here, arr_nums[1] + arr_nums[2] = 6

So, return [1, 2]

Let us use HashMap to solve this problem.


public int[] twoSum(int[] numbers, int target){

int[] arr = new int[2]; //an empty array to return the results

Map map = new HashMap();

/* map for numbers and index pair */

/* check if map has an elements which is equal to difference between current element and target */

for(int i=0; i<numbers.length; i++){

Integer val = map.get(target - numbers[i]);

if(val ==null){

map.put(numbers[i] i);

}else{

arr[0] = val;

arr[1] = i;

break;

}

}

return arr;

}

Time Complexity: O(N) , since the array has been traversed only once.

Space Complexity: O(1) + O(N), O(1) for variables and O(N) for the Hashmap.

Advertisements

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 )

Google+ photo

You are commenting using your Google+ 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 )

Connecting to %s