# Problem Statement:

``````Write a function that takes in a non-empty array of distinct integers and an
integer representing a target sum. If any two numbers in the input array sum
up to the target sum, the function should return them in an array, in any
order. If no two numbers sum up to the target sum, the function should return
an empty array.

Note that the target sum has to be obtained by summing two different integers
in the array; you can't add a single integer to itself in order to obtain the
target sum.

You can assume that there will be at most one pair of numbers summing up to
the target sum.

Sample Input
array = [3, 5, -4, 8, 11, 1, -1, 6]
targetSum = 10

Sample Output:
[-1, 11] // the numbers could be in reverse order
``````

# Note: See hints only if you are unable to solve the problem at least twice. Be astute.

Hint 1:

Try using two for loops to sum all possible pairs of numbers in the input array.
What are the time and space implications of this approach?

Hint 2:

Realize that for every number X in the input array, you are essentially trying to
find a corresponding number Y such that X + Y = targetSum. With two variables in
this equation known to you, it shouldnâ€™t be hard to solve for Y.

# Optimal Time and Space Complexity:

O(n) time complexity| O(n) space complexity - where n is the length of the input array

# Date 2nd July, 2022

#2 approaches used

``````def twoNumbersSum(array, targetSum):

# Approach 1: using HashTable
# TC = O(n)
# SC = O(n)
# Note: Approach 2 code is post this method

visited = {} # Dictionary for O(1) time access

for val in array: # O(n)
diff = targetSum - val
if visited.get(diff): # if difference is in visited then match found
return [val, diff]
visited.update({val: True}) # else, add a new entry into visited
# if no pair is found then return empty array
return []
``````

# SC = O(1)

``````def twoNumbersSum2(array, targetSum):
array.sort()
left  = 0 # Initialized to lowest value idx
right = len(array) - 1 # Initialized to highest value idx

while left < right: # worst case only one element remains i.e. left = right
left_val, right_val = array[left], array[right]
currentSum =  left_val + right_val
if currentSum == targetSum:
return [left_val, right_val]
elif currentSum < targetSum:
left  += 1
else:
right -= 1
return []
``````

# UnitTest.py

``````import TwoNumbersSum as program
import unittest

def test_case_1(self):
output = program.twoNumbersSum([3, 5, -4, 8, 11, 1, -1, 6], 10)
self.assertTrue(len(output) == 2)
self.assertTrue(11 in output)
self.assertTrue(-1 in output)

def test_case_2(self):
output = program.twoNumbersSum([3, 5, -4, 8, 11, 1, -1, 6], 20)
self.assertTrue(len(output) == 0)

def test_case_3(self):
output = program.twoNumbersSum2([3, 5, -4, 8, 11, 1, -1, 6], -5)
self.assertTrue(len(output) == 2)
self.assertTrue(-4 in output)
self.assertTrue(-1 in output)

if __name__ == '__main__':
unittest.main()
``````