Time complexity of python two-sum solution

Question

I have a question about the a widely accepted solution to the classic leetcode two-sum question, which reads as follows:

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice.

The solution I'm referring to iterates over nums and stores a mapping of values in nums to their indices. With each iteration over nums, we check if there is a complementary key to the current element in nums which would give us target, and if so we lookup and return its value:

    def twoSum(self, nums: List[int], target: int) -> List[int]:
        lookup = {}
        for i in range(0, len(nums)): 
            if target - nums[i] in lookup:
                return [i, lookup[target - nums[i]]]
            lookup[nums[i]] = i

Everyone seems to think this is an O(n) solution. However, I understand it to be O(n^2). For each iteration i, we're also iterating over potentially n-1 keys in the lookup table when we do nums[i] in lookup. Am I missing something?

Answer 1

As lookup is a dictionary, it doesn't linearly search through its keys when looking up a value. It uses a mathematical function (called a hash) to calculate the value's location using the input key. This is an O(1) operation, meaning that checking if nums[i] in lookup is also an O(1) operation.

If lookup were a list, then you'd be right in saying the algorithm was O(n²)

You can google "Python how do dictionaries work" or something similar to find out more. I found this as the first result :)