Ok im on a tablet so i ll keep it short. make an array up to sum/2. Scan thru the list. If u find int represented by array or its counter part, mark the the space. Eg 2+5 equals 7 if 2 or 5 comes along put that in 2. Now do that until u bump into 5 or other number before. U know? its easy just think bout it.

Isn't it just O(n) if you create a hash map? Here's my python implementation, returning 0 if it cannot find any pairs (this is what Rene said as well). Assuming first two means the first one and its corresponding number def findFirstTwo(sumValue, theArray): returnArray = [] sumHash = {} for x in theArray: sumHash[sumValue-x] = x for x in theArray: if (x in sumHash): return (x,sumHash[x]) return 0

linear sorting + linear search done

Store the values of the 'sum - array[index]' in a hash map as a key and Map the key to the value of the index. Then go through the array and if you find a value that is equal to the Array[index] you have found that that the value at that index and the value of the element that is mapped to the key's index are the first 2 numbers that give the given sum. This is O(n)

Sort the array. go with two pointers one from the begining and one from the end, each time comparing the sum and moving the pointers accordingly. the complexity is o(nlogn) which is the sort. package com.google.interview2; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.List; public class FindSum { public static int[] findSum(ArrayList array, int sum){ Collections.sort(array); int i=0, j=array.size()-1; while (i sum){ --j; } else { ++i; } } return null; } public static void main(String[] args) { List arr = new ArrayList(); arr.add(7); arr.add(-9); arr.add(1); arr.add(0); arr.add(79); int[] res = findSum((ArrayList) arr,7); if (res != null){ System.out.println("found "+res[0]+"+"+res[1]); } else{ System.out.println("not found"); } res = findSum((ArrayList) arr, 76); if (res != null){ System.out.println("found "+res[0]+"+"+res[1]); } else{ System.out.println("not found"); } } }

Sort the array. O(nlogn) take two pointer at head( index 0 ) and tail (index array.length-1) while (head sum) tail-- else print head and tail }

Here you go, an excuse for me to play a bit with Ruby and an excuse for you to learn it: def find2sum(array,desired_sum) the_hash=Hash.new i=0 array.each do |elt| complement = desired_sum-elt lookup = the_hash[complement] if (lookup == nil) the_hash[elt]=i else #puts "soln found, complement=#{complement} at index=#{lookup}, with #{elt} at #{i}" return [lookup,i] end i=i+1 end #puts "soln not found!" return[-1,-1] end puts find2sum([39,5,15,3,7,9,16,30,23],30)

Gave a O(n^2) solution by comparing each number to every other number, was asked to improve it. Build a binary tree out of the array, do a traversal of the tree, and use the fact SUM = A + B, where A is the node you are currently visiting. Do a binary search of B. Was asked to come up with a O(N) solution.