Problem Statement
Given an array of integer nums and an integer target, return indices of the two numbers such that they add up to the 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 <= 105
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.
Analysis
So, we have to find two numbers among all the numbers in an array such that when they are added, they give us a third number equal to the target.
For e.g.,
If nums = [2,7,11,15] and target = 9,
then we should return 2 and 7 because 2 + 7 = 9
In simpler words, we need to find -
c = a + b
where,
c => target
a and b => elements from the given array
Also, the given constraints suggest that there is only ONE valid answer along with the ranges of the elements in the array and the target.
After we have analyzed our problem, now it’s time to think about the solution.
Approach #1
The first solution that comes to mind is -
Take one element
Add this element with every other element
After adding, compare the sum with the given target
If the sum is equal to the target, return the indices of these two elements
If the sum is not equal to the target, we check for the next pair
Pretty simple, eh 😉? Let’s analyze the time and space complexities.
Time Complexity
Let’s say the array has n elements then -
For 1st element - we will check for (n - 1) elements
For the 2nd element - we will check for (n - 2) elements
For the 3rd element - we will check for (n - 3) elements
and so on...
Thus, the total iterations would be - [(n - 1) + (n - 2) + (n - 3) + ... + 2 + 1]
If we simplify the above expression we will get the -
n * (n - 1) / 2 = n2 - 2n ≈ n2
Thus, our time complexity would be - O(n2).
Space Complexity
Since we are not using any extra data structure hence our space complexity would be O(1).
This approach is simple and intuitive but it takes quadratic time which is bad for large inputs. Let’s see if we have an efficient approach to solving this problem. As a matter of fact, we do 😄!
Approach #2
In the earlier approach, we did what naturally came to us. But let’s try to really think through this problem. Hmm… 🤔
When we were analyzing the problem, we came across the following equation
c = a + b
but can we write the above equation as -
b = c - a
Of course, we can. We are mathematicians after all 😁.
The benefit of writing this equation is that now we can iterate through the array only once and calculate the difference between the target (c) and the current element (a) and find the other element (b). The idea is as follows -
Loop through the array
Check if we have encountered the current element before
If we have, we will return the index of this element and the index of the difference between the target and the current element. We will only encounter this element before only if we have saved the difference between the target and the element which when added to the current element gives the target itself. This is confusing I know but once it clicks, it’s very obvious.
If we haven’t, we will save the difference between the target and the current element.
Repeat the process
Since we need to store our difference, we need a data structure that can store the difference and their corresponding index. So what do you think, which data structure can help us? Of course, we need a Map where we will store the difference as a key and the corresponding index as a value.
Time Complexity
Since we are iterating the array only once, the time complexity would be O(n).
Space Complexity
Since we need a Map of the size of the array, the space complexity would be O(n).
Code
Now we have an approach to solving this problem, let’s write some code -
Java
Javascript
Kotlin
Python
Conclusion
We hope you liked this post. Here, we solved the very first problem on LeetCode in O(n) time and O(n) space