LeetCode: Two Sum (Solution in Python & Explanation)

In this article, I will be explaining how to solve the Two Sum problem on LeetCode. This is an Easy-level question for Arrays.

The 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]

The Solution

The most straightforward way to solve this problem is to check every combination of two values in the array and see if they can sum up to the target value. To do this, we would iterate through the entire array and for each item we would iterate through the array a second time to check the sums of the current array item with every other item in the array and see if they are the target. The (worst-case) runtime for this solution method is not very efficient: O(n2).

There is a better solution that only requires us to loop through the array once. Basically, if we could loop through the array and, for each array item, check if the number that adds with that value to get the target exists in the array using an operation that doesn’t have O(n) time complexity, then we could make our program much faster. We can do this by using a hash map.

We create a hash map that will store array items as keys and their indexes in the array as values ({array_value: array_index})

We use the enumerate function to get the index of the current item as we loop through the array. For each array item, we compute the difference diff between the target value and the item’s value. Since target - n = diff, that means diff + n = target. If this difference diff is in the hash map, then that means that the value has already been seen in the array. Thus, we’ve found the . If the difference is not in the array, then we add the current array item and its index to the hash map then move to the next array item.

def twoSum(self, nums: List[int], target: int) -> List[int]:
        hm = {} 
        for i, n in enumerate(nums): 
            diff = target - n 
            if diff in hm:
                    return [hm[diff], i]
            hm[n] = i

This solution has a time complexity of O(n) because we only have to loop through the nums array once and the lookup and insert operations into the hash map have a runtime of O(1). Although, we do have to use extra memory to create the hash map. The memory complexity is O(n) because we could potentially add every value to the hash map.