Complexity Analysis
def two_sum(nums, target):
seen = {}
for i, x in enumerate(nums):
comp = target - x
if comp in seen:
return [seen[comp], i]
seen[x] = i
return []What is the time and space complexity?
Work it out before scrolling down.
Time
O(n)
Space
O(n)
How to derive it
Single pass through n elements. Dictionary lookup (`in seen`) and insertion are both O(1) average. The dict stores up to n entries → O(n) space. This is the classic time-space tradeoff: O(n²) brute force becomes O(n) by spending O(n) space on a hash map.