Problem 1 - Two Sum (Easy)
Code for this problem can be found at https://github.com/scprogramming/LeetcodeExplained/tree/master/Problem%20One%20-%20TwoSum%20(Easy)
The Problem: Given an array of integers, return indices of the two numbers such that they add up to specific target. Assume that there exists exactly one solution, and that you may not use the same element twice.
Before starting to program a solution, we always want to think about what the problem is asking, and how we would solve it on paper. This will reveal the algorithm used to solve the problem.
So, let's start with an example instance of the problem. Suppose you are given the array [1,2,2,7], and a target value of 9. We want to find two numbers inside of that array that add up to 9.
How would you do something like this? One approach that works is to start at the first number, and try adding it to every possible number in the list, then repeat the same with the next number, until either a solution is found, or we run out of numbers.
Let's look at this with our current example. For [1,2,2,7], we start with the number 1 at the start of the list, and compute the sums of it and any other number.
1 + 2 =3
1 + 2 = 3
1 + 7 = 8
None of these are the solution we are looking for, so we go to the next number, 2. We then try adding it to every number as well and see if we get a solution.
2 + 2 = 4
2 + 7 = 9
At this point, we have a solution, at index [1,3]. Notice that I'm only computing the sums of the values that follow the current index. So, for 2, I don't compute any values with 1, since it comes before 2. This is because we already computed every possible combination with 1, so we don't need to do anything further with it.
After seeing this example, we can code a solution to the problem. First, let's discuss how we are going to iterate the list. We are going to use a nested while loop, like below:
There are a few things to understand here. First, we only need to iterate until we have found a single solution. Since this is the case, I've put a condition in the while loops to stop when a solution is found. The first while loop is determining which number to start at. Once we have that number, we move one index after it and loop the remainder of the list looking for the solution. The logic to look for a solution is as follows:
We check if the number at the index i, plus the number at index j is equal to the target. If it is, we found a solution, and we append it to the solution list. Otherwise, we move j forward and try the next number. We repeat until a solution is found, or we run out of values to check.
The full code is as follows:
The code is straightforward, but there are a few key things to remember:
- When we pick an i value, we set j to be i + 1, since we don't want to start checking at the value i, but rather the next available value.
- We use while loops since there is only one possible solution. If we find the solution, we should stop iterating, since there is no point in continuing.
If you are interested in discussing the time complexity of this algorithm, we can look at the worst case to see how it runs. Consider an example where we don't find the value, for instance [1,2,3,4] with a target of 31. We won't find the value, so the following work will be done:
Iterate [1,2,3,4] for a solution, then [2,3,4], then [3,4].
Each iteration, we do n - 1 addition, since the first value isn't added to itself. We will have to move the i index n - 1 times as well, meaning we have n - 1 subsets that get iterated n - 1 times. This gives us a time complexity of (n-1)(n-1), which is $O(n^2)$.
A natural question is, can we improve this algorithm at all? It turns out that we can do better in terms of time complexity, by adding hash tables into the algorithm. To get to this solution, we must redefine the problem in a slightly different way.
Let's return to the example from before, where we have [1,2,2,7] with a target of 9. Say we start with 1 again. Let's ask a simple question, what number must be added to 1 in order to get a value of 9. To find this, we simply take 9 - 1 = 8, so the answer is 8.
If we know this information, all we need to do now is scan the list for the number 8. If 8 exists, we know that it is a solution, otherwise, we move on.
Let's see how this can be implemented. We can define a hash table that holds all the values in the list. From here, we just determine what value will give us the target and scan the hash table for it. If we find it we are done, otherwise, we continue. The code for this looks like this:
First, we iterate the list to add all the numbers to the hash table. Then, we iterate the list a second time, this time taking the current number, determining what needs to be added to reach the target, and checking if that exists in the hash table. If it does exist, and isn't the same index as the current number, we are done. Otherwise, we check the next number in the list.
Looking at the time complexity, this is better. We iterate the list once to add the values to the hash table, which is n operations. We then at worst iterate a second time, checking for the value that makes the target sum, which is another n operations. Since the loop is no longer nested, and a hash table lookup is constant time, we have $O(n+n) = O(2n)$, meaning the time complexity is $O(n)$. This algorithm is now linear time, which has a better overall performance compared to the first algorithm.
The hash table solution would be the most optimal solution for this problem, so this solution should be used when encountering this problem.