# 1. Two Sum I

## Question

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].


## Solution

### O(n^2) solution

Loop through each element x and find if there is another value that equals to target−x.

class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
length = len(nums)

for i in range(0, length):
for j in range(i + 1, length):
if nums[i] + nums[j] == target:
return [i, j]


### O(n) solution

Use a hash table to look up the index of target−x for each x. When each x is inserted into the hash table, look up target-x.

class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
idx_dict = {}

for idx, n in enumerate(nums):
if n not in idx_dict:
idx_dict[n] = idx
elif n + n == target: # Duplicate only works when n is half of target
return [idx, idx_dict[n]]

if (target-n) in idx_dict:
other_idx = idx_dict[target-n]
if other_idx != idx:
return [idx, other_idx]


# Two Sum II - Input array is sorted

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.

Note:

• You may assume that each input would have exactly one solution and you may not use the same element twice.

Example:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.


## Solution

Use binary search to find the complement target-x. The time complexity is O(nlogn).

class Solution(object):
def twoSum(self, numbers, target):
"""
:type numbers: List[int]
:type target: int
:rtype: List[int]
"""
for idx, n in enumerate(numbers):
comp_idx = self.find_compliment(numbers, target - n, idx + 1, len(numbers))
if comp_idx != -1:
return [idx + 1, comp_idx + 1]

def find_compliment(self, numbers, target, start, end):
if end-start <= 1:
if numbers[start] != target:
return -1
else:
return start
else:
mid = int((end + start) / 2)
if numbers[mid] > target:
return self.find_compliment(numbers, target, start, mid)
elif numbers[mid] < target:
return self.find_compliment(numbers, target, mid, end)
else:
return mid


### Greedy Algorithm

We use two indexes, initially pointing to the first and last element respectively. Compare the sum of these two elements with target. If the sum is equal to target, we found the exactly only solution. If it is less than target, we increase the smaller index by one. If it is greater than target, we decrease the larger index by one. Move the indexes and repeat the comparison until the solution is found.

class Solution(object):
def twoSum(self, numbers, target):
"""
:type numbers: List[int]
:type target: int
:rtype: List[int]
"""
i = 0
j = len(numbers) - 1

while i < j:
sum = numbers[i] + numbers[j]
if sum < target:
i += 1
elif sum > target:
j -= 1
else:
return [i+1, j+1]



# 170. Two Sum III - Data structure design

Design and implement a TwoSum class. It should support the following operations: add and find.

• add - Add the number to an internal data structure.
• find - Find if there exists any pair of numbers which sum is equal to the value.

Example 1:

add(1); add(3); add(5);
find(4) -> true
find(7) -> false


Example 2:

add(3); add(1); add(2);
find(3) -> true
find(6) -> false


## Solution

class TwoSum(object):

def __init__(self):
"""
"""
self.count_dict = {}

"""
Add the number to an internal data structure..
:type number: int
:rtype: void
"""
if number not in self.count_dict:
self.count_dict[number] = 1
else:
self.count_dict[number] += 1

def find(self, value):
"""
Find if there exists any pair of numbers which sum is equal to the value.
:type value: int
:rtype: bool
"""
for n in self.count_dict:
if n + n == value and self.count_dict[n] >= 2:
return True
if n + n != value and value - n in self.count_dict:
return True
return False

# Your TwoSum object will be instantiated and called as such:
# obj = TwoSum()
# param_2 = obj.find(value)


# Two Sum IV - Input is a BST

Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.

Example 1:
Input:
5
/ \
3   6
/ \   \
2   4   7

Target = 9

Output: True

Example 2:
Input:
5
/ \
3   6
/ \   \
2   4   7

Target = 28

Output: False


## Solution

### 1

Walk the BST and find target-x using Binary search. This gives O(nlogn) time complexity.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def findTarget(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: bool
"""
stack = list()
node = root
while True:
# Numbers in BST are unique, so if a node is half of k, then it is not possible
if node.val * 2 != k and self.findComplement(root, k - node.val) == True:
return True
if node.left is not None:
stack.append(node.left)
if node.right is not None:
stack.append(node.right)
if len(stack) == 0:
return False
else:
node = stack.pop()

def findComplement(self, root, v):
node = root
while True:
if node.val == v:
return True
elif node.val > v and node.left is not None:
return self.findComplement(node.left, v)
elif node.val < v and node.right is not None:
return self.findComplement(node.right, v)
else:
return False



### Use Set to Record Seen Numbers

By traversing the tree, we can record seen numbers in a set, and for each number check whether target-x is in the set. This gives O(n) time complexity.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def findTarget(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: bool
"""
stack = list()
seen_number = set()
node = root
while True:
# Numbers in BST are unique, so if a node is half of k, then it is not possible
if (k - node.val) in seen_number:
return True
else:

if node.left is not None:
stack.append(node.left)
if node.right is not None:
stack.append(node.right)
if len(stack) == 0:
return False
else:
node = stack.pop()


### In-Order Traversal of BST

In-order traversal of BST produces the nodes in ascending order, reducing the problem to Two Sum II.