Problem Statement
With extra space allowed, what is the optimal time complexity to solve Two Sum on an unsorted array?
Explanation
Use a hash map from number to index while scanning once. For each value, check if target minus value exists in the map. This gives linear time because each lookup is constant time on average.
Sorting would make it O(n log n) and nested loops are quadratic. The hash map approach is the standard answer in interviews.
Code Solution
SolutionRead Only
def two_sum(nums, target):
pos = {}
for i, x in enumerate(nums):
y = target - x
if y in pos:
return pos[y], i
pos[x] = i
return None