Solution: Two Sum

Statement#

For the given array of integers arr and a target t, you have to identify the two indexes that add up to generate the target t. Moreover, you can’t use the same index twice, and there will be only one solution.

Note: We will assume that the array is zero-indexed and the output order doesn’t matter.

Constraints:

• $2 \leq$ arr.length $\leq 10^4$
• $-10^9 \leq$ arr[i] $\leq 10^9$
• $-10^9 \leq$ t $\leq 10^9$
• Only one valid answer exists.

Solution#

So far, you have probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach#

A naive approach for solving this two-sum problem would be to use two nested loops to check every possible pair of numbers in the array to see if their sum is equal to the target value. The outer loop will iterate over each number in the array, and the inner loop will iterate over all the remaining numbers in the array. For each pair of numbers that we check, we add them together and see if the sum is equal to the target value. If it is, then we have found the two numbers that add up to the target value, and we return their indexes. This naive approach uses only a constant amount of space, so the space complexity is $O(1)$, whereas the time complexity will be $O(n^2)$, where $n$ is the length of the input array.

Optimized approach using knowing what to track#

We will use a hash map to solve the two-sum problem because it allows us to perform lookups in a constant time, enabling us to quickly check if the difference between the target value and each value of the array already exists in the hash map. If the difference exists in the hash map, it indicates that we have found the two numbers that add up to the target value, and we can return their indexes. If not, we add the current number and its index to the hash map and continue iterating through the input array.

To implement this algorithm, we will first create an empty hash map to store the numbers and their indexes. Then, we will iterate over the input array, and for each number in the array, we will calculate its difference (the difference between the target value and the number). Next, we will check if the difference exists in the hash map as a key. If it does, we will retrieve the value of the difference from the hash map, which is the index of the difference value in the array and return it with the current index as the solution to the problem. If the difference is not in the hash map, we will add the current number as a key and its index i as a value to the hash map. We will continue iterating through the input array until we find a pair of numbers adding to the target value. Once we find such a pair, we will return their indexes.

Let’s look at the following illustration to get a better understanding of the solution:

Let’s take a look at the code for this solution below:

Solution summary#

The algorithm can be summarized in the following steps:

• Create a hash map to store the numbers and their indexes in the array.

• Iterate over the array and look up the difference between the target and the current number in the hash map.

• If the difference exists in the hash map, return the indexes of the two numbers. Otherwise, add the current number and its index to the hash map.

• Keep iterating through the input array until a pair of numbers that add up to the target value is found.

• Return the indexes of the pair.

Time complexity#

The time complexity of this algorithm is $O(n)$, where $n$ is the length of the input array.

Space complexity#

The space complexity of this algorithm is also $O(n)$, where $n$ is the total number of elements stored in the hash map in the worst case.