Community

Start a Thread


Notifications
Subscribe You’re not receiving notifications from this thread.

Two Sum (Main Thread)

Here is the interview question prompt, presented for reference.

This is a classic and very common interview problem. Given an array of integers, return the indices of the two numbers in it that add up to a specific goal number.

So let's say our 'goal' number was 10. Our numbers to sum to it would be 3 and 7, and we would return an array of indices 1 and 3 respectively.

let arr = [1, 3, 6, 7, 9];
let goal = 10;
twoSum(arr, goal);
// [1, 3]

You may assume that each input would have exactly one solution. Additionally, you may not use the same element twice towards the sum. This means if given [1, 3] and a goal of 2, you cannot use 1 twice and return its index twice as [0, 0].

Here's the function signature to fill in:

function twoSum(arr, goal) {
  return arr;
}

AlgoDaily partner CodeTips.co.uk has kindly provided a guide on solving Two Sum in Go. Check it out for even deeper coverage of this problem.

Constraints

  • Length of the array <= 100000
  • The values of the array will be between -1000000000 and 1000000000
  • The array can be empty
  • The target sum will be between -1000000000 and 1000000000
  • Expected time complexity : O(n)
  • Expected space complexity : O(n)

You can see the full challenge with visuals at this link.

Challenges • Asked almost 2 years ago by Noobert

Jake from AlgoDaily Commented on Jul 29, 2019:

This is the main discussion thread generated for Two Sum.

Noobert Commented on Jul 29, 2019:

function twoSum(arr, goal) {

let results = [];

for (let i = 0; i < arr.length; i++){

if (arr.indexOf(goal - arr[i]) > 0){

results.push(i, arr.indexOf(goal - arr[i]));

break;

}

}

return results;

}

Vishnu Lucky Commented on Dec 14, 2019:

private static int[] getIndices(int[] a, int k) {

HashMap map = new HashMap<>();
for(int i=0;i<a.length;i++) {
map.put(a[i], i);
}

for(int i=0;i<a.length;i++) {
if(map.containsKey(k-a[i])) {
return new int[] {i,map.get(k-a[i])};
}
}

return new int[] {-1,-1};

}

kcoddington Commented on Sep 17, 2020:

The following solution shows being faster than the provided solution on jsbench.me:

function twoSum(arr, goal) {
  const results = [];
  const hashmap = {};
  for (let i = 0; i < arr.length; i++) {
    hashmap[arr[i]] = i;
    const mate = goal - arr[i];
    if (hashmap[mate] != null) {
      results.push(hashmap[mate]);
      results.push(i);
      break;
    }
  }
  return results;
}
TimWong17 Commented on Jan 17, 2021:

Is there a difference in using the Two Pointer approach versus a Hash Map for this problem? I was initially using the Two Pointer approach to solve this. I believe there time complexities are both O(n). Just not too sure which approach would be best in an interview setting.

Jake from AlgoDaily Commented on Jan 19, 2021:

Hi Tim,

Both approaches work well! The hash map takes O(n) more space (since it needs to store each input element in the array as keys), so complexity-wise Two Pointers are better (O(1) space).

anil77k Commented on Jan 25, 2021:

The below solution seems to work fine. But when I submit the tests are being called for sortedtwosum.

public static int[] twoSum(int[] arr, int goal){
        int[] result = new int[2];
        HashMap<Integer,Integer> resultMap = new HashMap<Integer,Integer>();
        for(int i=0;i<arr.length;i++){
            if(resultMap.containsKey(arr[i])){
                result[0] = resultMap.get(arr[i]);
                result[1] = i;
                return result;
            }else{
                resultMap.put(goal - arr[i], i);
            }
        }
        return result;
    }
Jake from AlgoDaily Commented on Jan 25, 2021:

Thank you, Anil! This is resolved.