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 –

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 –

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%.