Python List Manipulation —Two Sum Problem

In this Challenge we will discuss how to solve the two sum problem in python, it’s a really good challenge to learn and often asked in interviews if you showed a good understanding of the basic pythonic stuff.

Given an array of digit and a number a target

A=[-2,1,2,4,7,11]

target = 13

Assumption:

• Each input has one solution
• You can’t use the same element from the array twice

Solution

We are going to consider three approaches here, each approach has it’s an optimization to the previous from memory management stand point.

The first approach: it’s the most naive one and the worst when it come to the complexity timeout. This approach called, brute force, it will take every element of the array and add it to the rest of the elements inside the array and check it the result equal to the target passed, if so print the result otherwise return False.

brute force approach will take time complexity as o(n²)

If we print it with passing the target = 13, we get the result as tuple of (2,11)

The second approach: This is an optimized solution that consider using the hash table to reduce the time complexity from n² to n. We can add each element of the array to a hash table, then we can check if the target minus the element is in the hash table, if that the case then we can return the tuple of the element and the last item we found in the hash table. if not we adding the element as a value for the key (target-element).

Using dictionary will get us a time complicity equal to n

When we run this code we’ll get the same answer but with a better time complexity this time.

The second approach: we going to use the sorting mechanism for out advantage, looping through the a sorted array could make it shrink the amount of looping if conditioned efficiently.

So after sorting, we will use two iterators, i and j. i considered the first element and j the last element. and we loop across to find if the first element + last element = target or not.

This approach use not data structure to store data, Time complicity = o(n)

If you they both equal then return both numbers, if the sum is less that the target move the first number to the next. the third case is when you have the sum bigger than the target them you need to move the last number to the previous one. again this approach only work with a sorted array.

and as expected we get the same results.

If you work the Right to left design or languages, or you know someone who do, then buying my book will be great way to gain RTL end to end knowledge and support me to keep writing book at the same time.

https://www.amazon.com/RTL-Foundations-Sam-Shamsan/dp/1656300087

This detailed solution is credit to Vincent Russo

The full source code can be found in his GitHub repo:

https://github.com/vprusso/youtube_tutorials/blob/master/data_structures/arrays/two_sum.py