Two Sum

Problem:

Given an array of integers and an integer target, find any 2 numbers in the list that add up to the target.

My first naive approach was to brute force it: for every number, iterate it against every other number and check to see if the addition matches the target. That is great, we will find the solution but its a very slow algorithm. It consumes n^2 processing cycles in the worse case scenario.

Trying to do better – initial thoughts:

  • If the target is greater than zero, we do not need to consider any number that is larger than the target.
  • If the target is small than zero, we do not need to consider any number that is smaller than the target.
  • Is the data organized in the data structure that we need? Maybe the algorithm is slow because it is constrained by the list/array of integers.
  • Is there any data structure that gives me O(1) access to the data? A map or a set could do the job but then how would the algorithm look like? Plus I would need to process the data to store it in the new data structure, that would take n cycles.

This did not come right away to my thoughts but after reading more about it I did understand it: the difference of any index in the array and the target can be found in the newly built set fairly quickly. If we do not find the data, then there is no answer. I also ignore any number larger than target.

Java solution

Not terribly bad – 2 for loops over n, so n+n(2n). Definitely better than n^2. The solution also traded processing for memory because now an extra Set is required.

Update and reminder to myself: at first I did not take into consideration negative numbers. My initial logic was discarding all negative numbers because of the logic: “we do not need to consider any number that is smaller than the target”. The previous logical statement works only when target is greater than zero. Funny enough by trying to optimize, I ended up making it more complicated and breaking the whole thing with any target less than zero.

Update #2: The optimization was actually breaking a case. What happens when the target is 10 and the array has numbers like 12 and -2?

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s