I’ve been doing the Algorithms: Design and Analysis Coursera course and during the final week there was a cool algorithm that needed to be coded called the 2 Sum algorithm.
I initially coded the naive implementation that would complete in O(n) time –
|
1 2 3 4 5 6 7 |
def twoSum(s, t): for x in s: testVal = t-x if testVal in s: print "x: {0} y: {1} t:{2}".format(x, testVal, t) return testVal return False |
This worked but we can do better!
First off we sort the input array, this allows us to modify the algorithm to take advantage of the data to modify our algorithm –
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
"""Assumes that s is sorted.""" def twoSumLinear(s, t): start = 0 end = len(s) - 1 found = False while not found and start < end: total = s[start] + s[end] if total == t: found = True elif total > t: end -= 1 elif total < t: start += 1 if found: print "x: {0} y: {1} t:{2}".format(s[start], s[end], t) return True else: return False |
This modification will still give a O(n) time in the worse case but on the given test data it decreased the running time by nearly 50%.
Questions? Comments?