2sum Solution
Solution
Approach 1: Brute Force
The brute force approach is trivial. We can easily loop through each element and at each element have a nested loop that looks for another value that can add up to the target. Take a look at the code below:
Complexity Analysis
-
Time complexity : . We first loop through the array and at each element we loop through the array again to find the complement which is time. Therefore, the time complexity is .
-
Space complexity : because we aren't using any extra memory.
Approach 2: Use a Hash Table
We can improve the run time complexity by using a more efficient way to check if the complementary number that adds up to the target value is in the array. If the complementary number is in the array, we need a way to find the index so we can return it as the output. The best way to do this would be to use a hash table.
We make a tradeoff for speed by storing the elements in memory. The hash table is the perfect data structure for this use case. The time complexity to look up a key in a hash table is on average O(1) because it stores it in memory already.
How should we store the keys in the hash table though?
The hash table will be stored as a mapping from the complement value to the index.
For example:
Given nums = [ 11, 2, 15, 7 ], target = 9.
First, initialize the hashTable as {}.
The first iteration we would look up 9 in the hash table but since it's empty we don't do anything. Now we want to populate the hash table with the complement mapped to the current index (0). The complement would be 9 - 11 = -2.
The hash table now looks like:
{-2 => 0}
The second iteration we would look up 2 in the hash table but since it doesn't exist we don't do anything. Now we want to populate the hash table with the complement mapped to the current index (1). The complement would be 9 - 2 = 7.
The hash table now looks like:
{-2 => 0, 7 => 1}
The third iteration we would look up 15 in the hash table but since it doesn't exist we don't do anything. Now we want to populate the hash table with the complement mapped to the current index (2). The complement would be 9 - 15 = -6.
The hash table now looks like:
{-2 => 0, 7 => 1, -6 => 2}
The fourth iteration we would look up 7 in the hash table and since it's already there. We get the value 7 is mapped to which would be the index of the original mapping and return it with the current index (3). We have now found the answer: [1,3]
So the algorithm would look like:
When iterating over the nums array at each iteration, i, we will want to first look up whether the key is in the hash table, if it is, then return get the current index along with the mapping of the key in the hash table. Otherwise, take the complement = target - nums[i] and store it in the hash table mapped to the current index.
Complexity Analysis:
-
Time complexity : . We iterate over nums which contains elements once. A look up in the hash table is time.
-
Space complexity : . The space used will depend on how many elements can get stored in the hash table. In the worst case we store all the elements in the list which is of size .