Two Sum

The question: You are given an integer array, and a target number. You need to find two numbers in the array that add up to that given target number. Assumptions — there is exactly one solution for each input and you may not use the same element twice.

Example: [1, 2, 3, 14], target = 4

Expected Solution: [0, 2] (NOTE: [1,1] also gives you a sum of 4, but as per the problem statement, this is not an acceptable solution)

Initial thoughts:

1. Is the array sorted? — well, that cannot be established with the problem statement. So, let’s assume the worst — it is an unsorted array.
2. Can there be repeated values in the array? — May be. It is not mentioned if the array is going to be unique, so let us assume that there can be duplicates.

Approach 1:

Considering the fact that the input array is not sorted, my reflexes were kicking in to sort the array. But, after a few failed attempts, it appeared that the approaches I had did not have a good enough pay off for the heavy initial investment of sorting the array. Therefore, we track back and take a different route.

This approach requires fast fetch operations and does not mind the order in which you provide the data. Maps seem to be the instinctive choice for such a solution. Each number in the array is checked if it is a possible solution by checking if the difference value (target-currentNumber) has already been encountered in the array (by checking if the map contains it). Else, add the currentNumber to this map for future checks.

//Approach 1.a
//Runtime: 3ms
//Memory usage: 39.3MB
public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int index = 0;
            for(int num : nums){
            if(map.containsKey(target - num)){
                return new int[]{map.get(target - num), index};
            }
            map.put(num, index++);
        }
        return new int[]{};
    }
/******************************************************************/
//Approach 1.b
//Runtime: 2ms
//Memory usage: 38MB
public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int index = 0; index<nums.length; index++){
            if(map.containsKey(target - nums[index])){
                return new int[]{map.get(target - nums[index]), index};
            }
/*Don't have to keep updating the HashMap if there are multiple values. A put() call can be expensive, so let's avoid it if we can*/
            if(!map.containsKey(nums[index])){
                map.put(nums[index], index);
            }
        }
        return new int[]{};
    }

This approach is definitely faster than the naive solution of comparing each number against the rest of the elements in the array. But, the trade off here is the space usage. Of course, there are many more approaches available out there. We’ll probably check them out in the upcoming posts.

Find more posts here.

Cheers & Chao!