Complexity Analysis
def count_pairs(arr, target):
count = 0
seen = set()
for x in arr:
if target - x in seen:
count += 1
seen.add(x)
return countWhat is the time and space complexity?
Work it out before scrolling down.
Time
O(n)
Space
O(n)
How to derive it
Single loop through n elements. Set lookup (`in seen`) and insertion (`add`) are both O(1) average. The set can grow up to n elements, so space is O(n). Total: O(n) time, O(n) space.