CODEWITHSUNDEEP
pythonsumnumbers
AKA DAMBOY
AKA DAMBOY

Reputation: 3

Two number sum : why don't anybody do it this way

I was looking for the solution to "two number sum problem" and I saw every body using two for loops and another way I saw was using a hash table

 def twoSumHashing(num_arr, pair_sum):
    sums = []
    hashTable = {}

    for i in range(len(num_arr)):
        complement = pair_sum - num_arr[i]
        if complement in hashTable:
            print("Pair with sum", pair_sum,"is: (", num_arr[i],",",complement,")")
        hashTable[num_arr[i]] = num_arr[i]

# Driver Code
num_arr = [4, 5, 1, 8]
pair_sum = 9    
  
# Calling function
twoSumHashing(num_arr, pair_sum)

But why don't nobody discuss about this solution

def two_num_sum(array, target):
    for num in array:
        match = target - num
        if match in array:
            return [match, num]
                 
    return "no result found"

when using a hash table we have to store values into the hash table. But here there is no need for that. 1)Does that affect the time complexity of the solution? 2)looking up a value in hash table is easy compared to array, but if the values are huge in number, does storing them in a hash table take more space?

Upvotes: 0

Views: 416

Answers (2)

Reza K Ghazi
Reza K Ghazi

Reputation: 168

First, the second function you provide as a solution is not correct and does not return a complete list of answers.

Second, as a Pythonist, it's better to say dictionary instead of the hash table. A Python dictionary is one of the implementations of a hash table.

Anyhow, regarding the other questions that you asked:

  • Using two for-loops is a brute-force approach and usually is not an optimized approach in real. Dictionaries are way faster than lists in Python. So, for the sake of time complexity, dictionaries are the winner.

  • From the point of view of space complexity, using dictionaries for sure takes more memory allocation, but with current hardware, it is not an essential issue for billions of numbers. It depends on your situation, whether the speed is crucial to you or the amount of memory.

Upvotes: 3

ordinov
ordinov

Reputation: 11

first function

uses O(n) time complexity as you iterate over n members in the array uses O(n) space complexity as you can have one pair which is the first and the last, then in the worst case you can store up to n-1 numbers.

second function

uses O(n^2) time complexity as you iterate first on the array then uses in which uses __contains__ on list which is O(n) in worst case. So the second function is like doing two loops to brute force the solution.

Another thing to point out in second function is that you don't return all the pairs but just the first pair you find. Then you can try and fix it by iterating from the index of num+1 but you will have duplicates.

This is all comes down to a preference of what's more important - time complexity or space complexity-

this is one of many interview / preparation to interview question where you need to explain why you would use function two (if was working properly) over function one and vice versa.

Answers for your questions

1.when using a hash table we have to store values into the hash table. But here there is no need for that. 1)Does that affect the time complexity of the solution?

Yes now time complexity is O(n^2) which is worse

2)looking up a value in hash table is easy compared to array, but if the values are huge in number, does storing them in a hash table take more space?

In computers numbers are just representation of bits. Larger numbers can take up more space as they need more bits to represent them but storing them will be the same, no matter where you store.

Upvotes: 1

Related Questions