Two Sum

This is a nice problem from LeetCode (Problem #1). This is also one of the most frequently asked questions in interviews.

Problem: 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.

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]

Example 3:

Input: nums = [3,3], target = 6

Output: [0,1]

Solution 1

An obvious and naive solution is to have two for loops, the first one pointing to the first number and the second one pointing to the second number. Whenever the first and second number add upto the target, we return their indices.

def twoSum(nums, target):
    for i in range(len(nums)-1):
        for j in range(i+1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]

Runtime: Due to the nested for loops, the runtime of this naive solution is $O(n^2)$.

Solution 2

We can actually construct an $O(n)$ solution using a hash-map. In Python, hash-maps are constructed using dictionaries.

def twoSum(nums, target):
    hashMap = {}
    for i in range(len(nums)):
        hashMap[nums[i]] = i

    for i in range(len(nums)):
        secondNum = target - nums[i]
        if secondNum in hashMap and hashMap[secondNum] != i:
            return i, hashMap[secondNum]

Note: In the case of an integer appearing twice in nums, the index of the second occurrence overwrites the first index in the dictionary. Do we need the first index also in our dictionary? No. This is because the first index is pointed to by i, and the second index is correctly pointed to by hashMap[secondNum], so we have indexes of both integers that sum up to target. Please see Example 3 above.

Runtime: The cost of building the hash map is $O(n)$ and the cost of finding the pair that sums to target is also $O(n)$. Hence the runtime is $O(n)$. The space complexity is $O(n)$ due to the need for the hash map.

Solution 3

Can we further improve Solution 2? Yes, we can - by making the following clever observation.

We don’t need to build the full hash map at the beginning. We initialize an empty hash map. Let’s say we are currently at element, nums[i] while iterating through the for loop. So, the second number that will sum up to the given target is secondNum = target - nums[i]. We check if secondNum is present in the hash map. If not, we add it to the hash map (as secondNum can sum up to another number further down in the for loop). We repeat the process until we find a matching number in the hash map.

The above idea helps avoid the need to build a hash map for all the elements in nums, thus saving on the space.

Following is the solution:

    def twoSum(nums, target):
        hashMap = {}
        for i in range(len(nums)):
            secondNum = target - nums[i]
            if secondNum in hashMap:
                return hashMap[secondNum], i
            else:
                hashMap[nums[i]] = i

Runtime: Both the time and space complexities are identical to those of Solution 2. The cost of building the hash map is $O(n)$ and the cost of finding the pair that sums to target is also $O(n)$. Hence the runtime is $O(n)$. The space complexity is $O(n)$ due to the need for the hash map.

Back to Hash Map Problems

---

anusha-murali.github.io