test

Two Sum

Two sum is a right of passage at this point. A cornerstone of fundamental algorithms. You just need to return the indices of two numbers which sum up to a target.  
 
Quick Solution

Keep track of which number is needed to complement the current number in the for loop. This can be done using a dictionary. Once a pair is found, return the two numbers as a list.  
 
Time Complexity

For loop: O(1)

Dictionary lookup: O(1)

Dictionary insertion: O(1)

Overall Time Complexity: O(N)  
 
Space Complexity

Dictionary: O(N)

Overall Space Complexity: O(N)  
 

  class Solution:
        def twoSum(self, nums: List[int], target: int) -> List[int]:
            complements = dict()

            for index, num in enumerate(nums):
                complement = target - num
                if complement in complements:
                    return [index, complements[complement]]
                complements[num] = index
            
            return [-1, -1]