Two Sum problem is considered easy and is frequently asked in Amazon phone interviews. We will see how we can start with a brute force solution and try to improve the code by introducing more data structures.
Problem Statement: Given an array of integers nums and an integer target return indices of the two numbers such that they add up to target
Our aim will be to reduce time complexity and space complexity.
The first solution that comes to mind is to go through the loop twice, each loop traverses the list, compares the sum of two numbers with the target, and returns the indices if the sum matches.
The time complexity of this algorithm is O(n^2)
. In this solution, we are not checking for null or multiple results because the question says, “the list returns one solution“.
class Solution: def twoSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ length = len(nums) for i in range(length): for j in range(i + 1, length): if nums[i] + nums[j] == target: return [i, j]
In our next solution, we can check whether the target-num[i] value exists in the rest of the list num[i+1:]
. This is a slightly better solution but still, the time complexity is not O(n)
.
class Solution: def twoSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ length = len(nums) for i in range(length): diff = target - nums[i] if diff in nums[i+1:]: index = nums[i + 1:].index(diff)+i+1 return [i, index]
Although the above method is faster than the first one, it is still not the best. Though it looks like we are looping once but in operator loops through the list to search for the diff variable.
If each lookup is the worst case, then O(n)
is the time complexity for the lookup. We are also using index
functions and slicing operations, which are very time-consuming, so we will ignore this solution as well?
Usually, these kinds of problems can be solved by using a hash map. Loop through the list and add all the numbers in the hash with number as the key and index as the value. Now loop through the list again and check the diff existence in the hash, and returns the indices.
class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: """ :type nums: List[int] :type target: int :rtype: List[int] """ _dict ={} for i, num in enumerate(nums): _dict[num] = i for i, num in enumerate(nums): num_b = target - num if num_b in _dict.keys(): return [_dict[num_b], i]
Now the complexity of the above problem is O(n)
. We can improve the above algorithm by removing a loop. Here we will loop through the list once. Look for the diff number in the hash for every element in the list.
if the diff number is not present in the hash, add the number and move on to the next one. Let’s see how to do it in the code.
class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: """ :type nums: List[int] :type target: int :rtype: List[int] """ _dict = {} for i, num in enumerate(nums): if target-num in _dict.keys(): return [_dict[target-num], i] else: _dict[num] = i