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:
- Your returned answers (both index1 and index2) are not zero-based.
- 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
Binary Search
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):
"""
Initialize your data structure here.
"""
self.count_dict = {}
def add(self, number):
"""
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()
# obj.add(number)
# 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:
seen_number.add(node.val)
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.