educative.io

Educative

Question about alternate approach

Why are we using a hash table to store the numbers given that we have a list as input? We can do this to save O(N) space, right?

def pair_with_targetsum(arr, target_sum):
for num in arr:
target = target_sum - num
if target in arr:
return [arr.index(num), arr.index(target)]
return [-1, -1]

1 Like

Because we want to use a map or dict to store the key rather than use a list. In your code, “if target in arr:” cost O(n), which cost the total time complexity is O(n^2) because we find one key in a list, but the code given, “if target_sum - num in nums:”, cost O(1) since it uses dict.

1 Like