Leetcode 1: Two Sum problem – Multiple Solutions

Two Sum problem is considered easy and is frequently asked in Amazon phone interview. We will see how we can start with brute force solution and try to improve the code by introducing more data structures.

The first solution that comes to the mind is to go through the loop twice, each loop traverse the list, compares the sum of two numbers with target and returns the indices if 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 rest of the list num[i+1:]. This is 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 kind of problem can be solved by using a hash. Loop through the list and add all the numbers in 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 returnt 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 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
Scroll to Top