# 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.

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

# Solution 1. Time complexity: O(n**2), Space complexity: O(1)
# Use nested loops to iterate over the array such that distinct integers
# are selected, and check if they sum up to the target number.
def two_number_sum_1(arr, target):
	for i in range(len(arr) - 1):
		for j in range(i + 1, len(arr)):
			if arr[i] + arr[j] == target:
				return [arr[i], arr[j]]
	return []

# Solution 2. Time complexity: O(n), Space complexity: O(n)
# Use a set for O(1) lookups. Since we need to find two numbers x, y such
# that x+y = target, when x is selected we check if target - x = y is
# present. If it is, then [x, y] is the result. If not, then we add x to
# the set and continue to the next element.
def two_number_sum_2(arr, target):
	seen = set()
	for i in arr:
		if (target - i) in seen:
			return [i, target - i]
		seen.add(i)
	return []

print(two_number_sum_1([3, 5, -4, 8, 11, 1, -1, 6], 10))
print(two_number_sum_2([3, 5, -4, 8, 11, 1, -1, 6], 10))