Two Number Sum - algoexpert.io

twoNumberSum1.py

"""
https://www.algoexpert.io/questions/Two%20Number%20Sum

O(nlogn) time | O(1) space
This algorithm sorts the arrays and then puts two index 
pointers at the edges and then advances towards the 
middle to find a solution.
"""
def twoNumberSum(array, targetSum):
	# sort array (really a list) first
	array.sort()
	
	# initialize the left index
	left = 0
	
	# initialize the right index
	right = len(array) - 1 # zero-indexed
	
	while left < right:
		currentSum = array[left] + array[right]
		
		if currentSum == targetSum:
			return [array[left], array[right]]
		
		elif currentSum < targetSum:
			left += 1
		
		elif currentSum > targetSum:
			right -= 1
	
	# return empty array
	return []

twoNumberSum2.py

"""
https://www.algoexpert.io/questions/Two%20Number%20Sum

O(n) time | O(n) space

The idea of this solution is to keep track of "potential matches".

If the target sum is 10 for example, and the current number is 11,
then the potential match would be: 

10 - 11 = -1

Check if -1 has been SEEN, if it hasn't been SEEN, 
put 11 in the SEEN array. 

Later, if -1 is the  current iteration of a number, 
it'll take the difference:

10 - -1 = 11

and check if 11 is in the SEEN array, which it will be and the
function will return with the current number and the potential
match.

Membership testing is faster with a dict than a list.
"""
def twoNumberSum(array, targetSum):
	# use dict for O(1) access time (dicts are based on hashing)
	# Python lists have O(n) access time
    seen = {}
	
	for num in array:
		potentialMatch = targetSum - num
		
		if potentialMatch in seen:
			return [potentialMatch, num]
		else:
			seen[num] = True
	
	return []