Categories

Leet Code: Two Sum

Author: Jason Smith

Greetings programs!

The LeetCode problem we will be tackling in this post is Two Sum. It is classified as an easy problem, so it is a good place to get our feet wet.

Problem Description


Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Constraints:

  • 2 <= nums.length <= 104
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109
  • Only one valid answer exists.

Solution One

So the first thing that pops out at me is that we are guaranteed an answer for every problem and it is an array of two indices. So the quick and dirty solution is to create two loops and just check every combination of two values until we find a solution. Each loop through the array is a complete loop so it gives us O(N^2) for our runtime and O(1) for our memory since we don't use anymore memory than was needed to loop and store our answer.

That was pretty easy and this is a fine answer if you have a machine that has low memory requirements but don't care about time. They do ask if we could come up with a better way to handle this that would run much faster, O(N).

Solution Two

To speed things up we will need to store some partial answers. If we take our target value and subtract the value at the current index we are at we will be given the value we need to find to match. If we store this in a HashMap with the key being the value we have to find and the data being the current index, then whenever we check a new index we just need to see if it is in the HashMap first and if it is, then store our index in our answer array and return it.

This will take O(N) time, but also take O(N) additional memory. This is a great all around solution for most machines as space is not as big of a concern.

Conclusion

That was a simple problem. It let me get my feet wet and allowed me to make sure my entire setup is working for these blog posts. There is a video of me solving this problem as well. The link is at the top of the post.

End of Line