CODEWITHSUNDEEP
pythonoptimization
Wyman Gray
Wyman Gray

Reputation: 31

sumOfTwo Time Limit Exceeded CodeFights Interview Practice

I am attempting the sumOFTwo challenge on CodeFights.com but I unfortuantly cannot complete it to view the solution. All my tests suceedd until the 15th hidden test and it says it exceeds the time limit.

The challenge is - You have two integer arrays, a and b, and an integer target value v. Determine whether there is a pair of numbers, where one number is taken from a and the other from b, that can be added together to get a sum of v. Return true if such a pair exists, otherwise return false.

My code is - 

def sumOfTwo(a,b,v):
    a.sort()
    b.sort()

    if(0 in a and v in b):
        return True
    elif(v in a and 0 in b):
        return True
    else:
        for i in a:
            for j in b:
                if(i + j == v):
                    return True
    return False

I know it could be shrunken down to about 6 lines of code, but I kept adding in lines that could help the code possibly finish quicker. Are there any other optimizations I am missing.

Upvotes: 3

Views: 3697

Answers (4)

AnaTol
AnaTol

Reputation: 59

Here is how I solved it in Python:

 def sumOfTwo(a, b, v):
        #No need to iterate a huge list, if the other list is empty
        if not a or not b:
            return False
        
        #kill duplicates
        b = set(b)
        
        #iterate through list a to look if the wanted difference is in b
        for x in a:
            if (v-x) in b:
                return True
        return False

Upvotes: 2

Md. Maksudul Islam Prince
Md. Maksudul Islam Prince

Reputation: 1

Try this:

function sumOfTwo(a, b, v) {
if(a.length==0)return false;
if(b.length==0)return false;
for(var i=0; i<a.length; i++){
     if(b.indexOf(v-a[i])>0){
        return true;
    }
}
return false;}

Upvotes: -1

user208145
user208145

Reputation: 379

This is what I have. It passes all the tests, hidden included, but it takes too long on four of the hidden tests.

def sumOfTwo(a, b, v):
  for i in a:
    if((v-i) in b):
      return True
  return False

@niemmi's answer passes the time limit portion. I didn't know sets were faster than arrays/lists. Thanks, good to know. If I add b=set(b) before the for loop, it passes.

Upvotes: 0

niemmi
niemmi

Reputation: 17263

You could just turn one of the lists to set, iterate over the other list and see if v - value_from_list exists in the set:

def sumOfTwo(a,b,v):
    b = set(b)

    return any(v - x in b for x in a)

print(sumOfTwo([3, 6, 7], [2, 1], 9))
print(sumOfTwo([3, 6, 7], [2, 1], 10))
print(sumOfTwo([3, 6, 7], [2, 1], 4))
print(sumOfTwo([3, 6, 7], [2, 1], 3))

Output:

True
False
True
False

Time complexity of above in O(n).

Upvotes: 9

Related Questions