2️1. Two Sum

Easy | Grind 75 | August 11 Thursday, 2022

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.

You can return the answer in any order.

Constraints

• 2 <= nums.length <= 10^4

• -10^9 <= nums[i] <= 10^9

• -10^9 <= target <= 10^9

• Only one valid answer exists.

Example 1

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2

Input: nums = [3,2,4], target = 6
Output: [1,2]

SOLUTION

Given a list of numbers and a target, we need to find two numbers in the list that sum to the target and return their indices. The naive n*n solution would be to iterate over the element and make a sum combination with every other element. Better solution: for every element there is one and only one unique element that adds up to the target. For instance, in example one, the target is 9 and the first element is 2. For element 2 to sum up to 9, you always need a 7. Similarly, if your element is 7, you need a 2. The compliments for a particular target always have a one-to-one relationship. If 2 and 7 make up 9, you won't find another number that summed with 7 makes up 9.

Using the above idea, we will start with an empty dictionary that will hold all the elements we have seen. While we iterate over the list, we will check if the target - current element is in the dictionary(have we seen this before) . If it is in the dictionary, we have found two elements that make up the target value.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # store the seen elements and their index
        compliments = {}
        
        for i in range(len(nums)): 
            # we have found two values that make up the target
            if target-nums[i] in compliments: 
                return [i, compliments[target-nums[i]]]
            else: 
                compliments[nums[i]] = i

TIME AND SPACE COMPLEXITY

TIME: O(n) where n is the length of the list. We iterate over all the elements once

SPACE: O(n) In the worst case, our compliments have be the last two elements. In that case we will have to store all the elements in the list in our dictionary.