Two sum problem python – Understanding the Two Sum Problem

Two sum problem python: The two sum problem is a  very common interview question, asked in companies.For the two sum problem we will write two algorithm that runs in O(n²) & O(n) time.

Two Sum Problem

Given an array of integer return indices of the two numbers such that they add up to the specific target.

You may assume that each input would have exactly one solution and you are not going to use same element twice.

Example:

Given numbers=[ 3 , 4 , 6 ,7 ] , target = 7,

Because num[0]+num[1] = 3 + 4 = 7,

return[0,1]

• Harshad Number in Python
• Python Interview Questions on Algorithm Analysis and Big-O
• Python Program to solve Maximum Subarray Problem using Kadane’s Algorithm

Example has given above we have to execute two sum problem for any two number in list and give us targeted value.

There are mainly two way to execute two sum problem.

1. Using Naive Method
2. Using hash table

Implementing Naive Method:

In this method  we would be loop through each number and then loop again through the list looking for a pair that sums and give us final value. The running time for the below solution would be O(n²).

So for this we will write an algorithm which mentioned below-

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

    return None            

test = [2,7,11,15]
target = 9
print(twoSum(test,target))

Output:

C:\New folder\Python project(APT)>py twosum.py
[0, 1]

C:\New folder\Python project(APT)>

So you can see that it has return us those indices which has given target value.If we change the target then value and indices both will change.This is what we want to do but it increases the complexity because we run two loop.

So for increasing complexity we will use second method which is hash table.

Implementing hash table:

Below we will show use of hash table. We can write an another faster algorithm that will find pairs that sum to numbers in same time. As we pass through each element in the array, we check to see if M minus the current element exists in the hash table.

Example:

If the array is: [6, 7, 1, 8] and the sum is 8.

class Solution:
    def twoSum(nums,target):
        prevMap = {}

        for i,n in enumerate(nums):
            diff = target - n
            if diff in prevMap:
               return[prevMap[diff],i]
            prevMap[n] = i
        return    
    nums=[6, 7, 1, 8]
    target= 8
    print(twoSum(nums,target))

Output:

C:\New folder\Python project(APT)>py twosum.py [1, 2] 
C:\New folder\Python project(APT)>

So you can see that above program gives us index value of the two number which gives us our target value.

Conclusion:

Great!So in this article we have seen two methods for two sum problem in python.Naive method has complexity O(n²)and Hash metod has complexity O(n),So best approach is Hash method and worst is Naive method.