LeetCode #1 — Solving the Two Sum Problem
Find more useful articles at www.davidseek.com
The two sum problem is a classic coding challenge required in many tech interviews, and the #1 challenge on leetcode.com.
Usually, one is given an unsorted array of integers and a target integer. In this scenario, your goal is to write an efficient algorithm that returns if there are two elements in the array that add up to the target. You are required to either return the indices or the integers themselves.
The example in this post assumes that there will be an answer and there will only be one pair that sums up to the target.
In your potential interview, it is important that you specifically ask your interviewer if they would like you to return all pairs, only the first pair, or what they want you to return if there is no pair at all.
The Brute Force Solution
The “brute force solution” is the least efficient way of solving any problem. It has the worst time/space complexity–but, it is a solution. However, it is better than nothing if you are unable to come up with a more advanced approach, and you may score points by being able to be coached into the proper direction.
For this example, we are going to use nested loops. There is an outer loop that iterates through every element and an inner loop to find two elements that sum up to k.
The time complexity of this approach is O(n²). As an example: If there are 100 elements in the array, you iterate 100 * 100–1, in short 100² or O(n²).
Now, let’s look at a more efficient solution. Efficiency is important when considering scalability. For example, the array could contain thousands or millions of elements.
Hash Map for a Linear Solution
Using a Hash Map, store every element of the array in the map and check if there is an element in the map/dictionary that–with the element at current index–sums up to k.
This is the best solution with a linear runtime. At most, we are checking every element once. The downside of this solution (which your interviewer may ask) is, that it requires O(n) space, given that we potentially need to store every element in the dictionary/hash map.
My Take:
We can always buy more space… We can always buy more memory… but we can’t buy more time.
Where to go from here?
I’m going to write many more blog posts about leetcode coding challenges and the tech interview process in general. Aside from my content I can highly recommend reading the book “Cracking the Coding Interview” and the course “Grokking the System Design Interview”.
I’m in no way affiliated with those two resources and/or links, but besides from YouTube and leetcode, those two helped me the most.
Find more useful articles at www.davidseek.com
