Pfthb

I am not an algorithm person, so pardon the naivety of the question.

I have a list A containing elements 100K elements. I have another list B containing 100K elements. Let's say a is an element from list A, b is the element from list B. I want to find out those (a, b) combinations whose sum is less than 100.

One obvious way to do this is following:

results = 
for a in A:
 for b in B:
 if (a+b) < 100:
 results.append((a,b)) 

but the time complexity of this approach is O(n*m) = 100K * 100K which is quite large. Is there any fast algorithm which can compute the desired output more efficiently - in terms of memory and time. If yes, can it be implemented in python?

Sort both lists (O(n log n) and O(m log m), maybe less if the values are constrained).

Then, you can simply find, for each a in A, the largest b in B such that (a+b) < 100. Every smaller b will also satisfy that condition.

Finding the largest b for some a can be done using binary search to find a lower bound in B. And by starting with the largest a going down, you can preserve the list of bs corresponding to the previous a, since the sum is going to be smaller.

No you can't get better than that in the worst case. Consider a pathological case where every combination of A and B must be appended to the list:

A = list(range(0, -n, -1))
B = list(range(0, -m, -1))

Because each pair must be appended, you are doing O(m * n) operations.

If you only needed to count the number of combinations this could be a different story.

As your criteria is that a + b < 100 that can be defined as range. In this case I defined it as wanted_result_range = range(0, 100) as your lists A and B are containing only positive numbers so results will be only positive values.

Run the following script and you will see how much faster is my approach than "frontal" one that you have mentioned. My solution will be bad if wider wanted_result_range is defined.

import timeit
# http://docs.python.org/3.3/library/timeit.html

print "nTiming execution timesn"

version1="""
results1 = 
list_A = range(1000)
list_B = range(1000)
wanted_result_range = range(0, 100)
d1 = 
l3 = 
for key in list_A: 
 d1[key] = True # Value associated to key is not important and can be any value 
for wanted_result in wanted_result_range:
 for key2 in list_B: 
 if ((wanted_result-key2) in d1): 
 results1.append((key2,wanted_result-key2))
"""
print("Version 1 - Hash table (dictionary) approach")
print(timeit.repeat(version1, number=10, repeat=4))
print('END Version 1n')

version2="""
results2 = 
list_A = range(1000)
list_B = range(1000)
for a in list_A:
 for b in list_B:
 if (a+b) < 100:
 results2.append((a,b))
"""
print("Version 2 - Frontal approach")
print(timeit.repeat(version2, number=10, repeat=4))
print('END Version 2n')