Ytukyg

I am running below code for getting indexes of two numbers from the input list whose sum is equal to target.

import itertools



class Solution:

   def twoSum(self, nums, target):

        combs = set(itertools.combinations(enumerate(nums), 2))

        while combs:

           elem = combs.pop()

           if int(elem[0][1]) + int(elem[1][1]) == target:

               return [elem[0][0], elem[1][0]]



cls = Solution()

nums = [3,3]

lst = cls.twoSum(nums,6)

print(lst)

It runs fine till input array is small, but when it grows to thousands of number, am getting Memory Limit Exceed. I believe there should be some other optimised way to do it.

Well because we cannot have array/ consecutive memory blocks more than 10^6 or 10^7

If we have Multidimensional array size will reduce to Matrix[1000][1000] to get total ~10^7 blocks

Itertools generate all possible pairs which could be exponential, and storing it in the set will definately overflow both in time and space.

So Solution to this would be improve the algorithm in both time and memory complexity.

one of the way to solve this problem is by hashing,

Basic idea is
A + B = target, where A,B are elements of an array

so we maintain hashtable with, key = element and value = index

and iterate to find if B = target - A, is present in the array, if found we print index of (A,B)

class Solution:

    def twoSum(self, nums, target):

        hashtable = dict() # key = number , value = index

        n = len(nums)

        lst = 

       for i in range(n):



           if(hashtable.get(target-nums[i],None) is None):

           # not found so update the hashtable

               hashtable[nums[i]] = i

           else:

           # pair found

               lst.append((hashtable[target-nums[i]],i))



        return lst



cls = Solution()



nums = [3,3]

lst = cls.twoSum(nums,6)



print(lst)