[Python] Couldn't understand on how lookup in a hashmap is O(N) while iterating over the same...

I was doing leet code and came across https://leetcode.com/problems/two-sum/description/, which I've tried solving with a seen counter using hashmap. Below is the code:

class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
#nums=[i for i in nums if i<target]
hashm={}
hashm[nums[0]]=0
for i in range(1,len(nums)):
if (target-nums) in hashm.keys():
return [hashm[target-nums],i]
hashm[nums]=i


I was curious on how good it was, so when I checked the Time complexity which I expected would be O(N^2), surprisingly in some checkers and even in leetcode it shows as O(N).

If we are iterating over a loop (which is O(N)) and at the same time if we do a lookup (for which I think it should be taking close to O(N) again) shouldn't it be O(N^2) solution?

Continue reading...