# Problem

• 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 + nums = 2 + 7 = 9, return [0, 1].

Note:
• Each element in the result should appear as many times as it shows in both arrays.
• The result can be in any order.

# Thought Process

• create a dictionary to store the data where k = data, value = data index
• for num in dictionary, check if target - num exists in the rest of the array, if exist return the index of num and target-num
• the problem assumes each input would have exactly one solution, however just in case there's no solution return false

## issues

• however, there are issues with this solution, if there are repetitive elements, then we will have collision, the new element will replace the previous element
• the root cause of this issue is bc we put all elements into the hash table all at once, the search can be a dynamic process as below:
• for any given state:
• at index i, we move to value v, all elements before v were moved into the hash table already
• if target - v exists in the hash table, return [i, ht[target-v]]
• else i = 1, so new v will replace the old v, since the problem assumes only 1 solution, we can confirm that:
• * [v, v] wont be a solution * after new v replace old v, it doesn't matter which v is used for a potential solution that v w = target * however, if the problem asks for all the solutions, it requires a different ds, maybe a stack?

# White Board

Below is the white board:

# Code

class Solution:
def two_sum(self, nums, target):
res_d = {}
for i in range(len(nums)): #O(n)
substrate = target - nums[i]

if substrate in res_d:
return [i, res_d[substrate]]
else:
res_d[nums[i]] = i

return False

def test():
nums = [3, 3]
target = 6
ts = Solution().two_sum(nums, target)

print(ts)

test()


[1, 0]

# Complexity

• when move array into a dict, time complexity is O(n); hash table search is O(1); so overall time complexity is O(n)
• Space complexity is O(n), as I created both a dict to store results

# Optimization

This is not an optimization, more of an alternative thinking. If we sort the array first, I can use two pointers, l, r:
• since sorting will destroy the order, so make a copy of nums, nums2: O(n)
• l = 0, r = len(nums) - 1
• while l < r
• if nums[l] + nums[r] == target, return [nums2.index(nums[l]), nums2.index(nums[r])]
• elif nums[l] + nums[r] < target, l += 1
• else r -= 1
class Solution2:
def two_sum2(self, nums, target):
nums2 = nums.copy()
nums3 = nums.copy()
nums = sorted(nums)
l, r = 0, len(nums)-1
while l <= r:
if nums[l] + nums[r] == target:
if nums2.index(nums[l]) != nums2.index(nums[r]):
return [nums2.index(nums[l]), nums2.index(nums[r])]
else:
nums3[nums2.index(nums[l])] = None
return [nums2.index(nums[l]), nums3.index(nums[r])]
elif nums[l] + nums[r] < target :
l += 1
else:
r -= 1

return False

def test_two_sum2():
# nums = [2,7,11,15]
# target = 9
nums = [3,2,4]
target = 6

inter = Solution2().two_sum2(nums, target)
print(inter)

test_two_sum2()


[1, 2]

We need to sort the arrays first, in python the time complexity for sorted method is O(nlogn), space complexity is O(n) as we need additional ds to store the results.