Two Sum - Leetcode #1 Short & Simple Solution
Updated: Jun 17, 2022
Problem Statement
This is another article in the series leetcode problem solutions and this article is a solution to leetcode 1 two sum problem.
Once you have a good understanding of two sum problem, it should help you solve advanced level problems like three sum which in some ways a continuation of the two sum problem.
Consider you are given an array of integers and a target sum, return indices of two numbers in the array such that they add up to the given target. You may assume that each input would have exactly one solution. Also, you cannot use the same element twice. You are allowed to return the answer in any order.
Example
Example 1:
Input: nums = [7,2,13,11], target = 9
Output: [0,1]Example 2:
Input: nums = [7,3,5], target = 8
Output: [1,2]Solution
Let us try to understand the problem statement first. Here we are given an array of integer elements and a target sum. Our job is to write an algorithm which returns indices of two elements in this array such that, when we add these two elements it should be equal to the target sum given.
For instance, in example 1 [7,2,13,11] is the given array and the given target sum = 9. If we take a look at the given array, the pair which adds to the target sum 9 is (7,2) i.e. 7+2 = 9. So our algorithm should return (0,1) as the result because these are the indexes of elements 7 and 2 respectively in the given array.
Similarly for the array in example 2 [7,3,5] output is (1,2) because these are the indexes of elements 3 and 5 respectively which add up to the target sum 8.
Note: If there are multiple such pairs we need to return the indexes of first pair we find from left.
It is stated in the problem statement that we can return the indices in any order, what does this mean? Let us understand this with example 1. The output for this example is [0,1], so when the problem statement says we can return the indices in any order what it means is that we can return either [0,1] or [1,0] as our output, both will be considered correct. Same for example 2, we can return either [1,2] or [2,1].
Solution 1: Brute Force
A straight forward solution to this problem is to check for every possible pair present in the given array.
For a given input array nums we need to do the following steps:
Run two loops and check for every combination in the given array.
Fix the outer loop at a specific index and move the inner loop to get all the possible pairs. The outer loop runs from i=0 to i=n-2 and inner loop runs from j=i+1 to j=n-1.
In each iteration of the inner loop check if the numbers represented by the outer and inner loop indexes add up to the target sum.
If nums[outerLoopIndex] + nums[innerLoopIndex] is equal to target, return {outerLoopIndex, innerLoopIndex} as result. Else continue iteration to check for the next pair.
Repeat the above steps until you find a combination that adds up to the given target.
For example, for array [7,2,13,11] and target sum 24, we fix the outer loop at index i=0 i.e element 7 and check it with all possible values of the inner loop from j=i+1 to j=n-1, i.e from index 1 to 3. So, we will be checking the following pair of elements in the first iteration of outer loop: (7,2) (7,13) and (7,11). Now we increment the outer loop index i by 1 and check it with indices 2 to 3 (i+1 to n-1) of the inner loop. We repeat this until we find the required answer.
Note: n here is the size of the array.
Code
Language: Go
In the worst case, this algorithm has a running time complexity of O(n^2). The worst case would occur when the required combination is the last combination to be checked by our loops.
Complexity Analysis
Time Complexity: O(n^2) Space Complexity: O(1)
Want to master coding? Looking to learn new skills and crack interviews? We recommend you to explore these tailor made courses:
Solution 2: Using Hashmap
It is possible to solve this problem in linear time. The idea is to make use of a hashmap to store the indices of the elements that are already visited. Hashmap "key" is the number in the given input array (You add this to the hashmap as you visit each element). Hashmap "value" is the index of the number in the array represented by the hashmap key.
For a given input array this algorithm does the following steps:
Create a hashmap which accepts integer datatype as key and value.
Iterate through each element in the given array starting from the first element.
In each iteration check if required number (required number = target sum - current number) is present in the hashmap.
If present, return {required number index, current number index} as result.
Otherwise add the current iteration number as key and its index as value to the hashmap. Repeat this until you find the result.
Simulation
Consider you are given the below input array and target = 24.
Let currIdx be the variable representing current element under process and let idxMap be our index map. Cells marked in orange indicate the currently processed array element.
At the beginning, currIdx = 0 and idxMap is empty as shown in first figure below. Next we check if the required number = target - current number is present in the idxMap.
Required number = 24 - 7 = 17 is not present in our hashmap, so we add 7 as idxMap key and 0 as idxMap value (0 is the index of 7 in input array) as shown in figure 2 below.
Next we move on to the second element in the array by incrementing current index. So currIdx = 1 which points to element 2 in array. Again we check if required number is present in idxMap, required number = 24 - 2 = 22 is not in our hashmap so we add to 2 to the hashmap along with its index 1.
Increment current index, currIdx = 2, which is element 13 in input array. Again required number = 24 - 13 = 11 is not in hashmap. Add {13:2} to idxMap. Same is shown in below diagram.
Our hashmap now contains 3 elements 7, 2 and 13 along with their indexes. Again we increment currIdx, currIdx = 3 which is element 11 in array.
Now required number = 24 - 11 = 13 is present in idxMap (shown by cell highlighted in green in the second figure below). That means we have found the pair which adds up to the target sum 24, i.e. (11 , 13). Therefore we return the indexes of 11 and 13 as our result. Index of 11 is nothing but currIdx which is 3 and index of 13 can be found from hashmap which is 2, therefore we return (3 , 2) or (2 , 3) as our result.
Code
Language: Go
Language: Python
Language: Java
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
The running time complexity of this solution is O(n) since we would have to go through all array elements in the worst case. As described in two sum solution 1, the worst case occurs when the required combination is the last combination to be checked.
Also the auxiliary space required is O(n) since we store the array elements in hashmap and in the worst case we would end up storing all values in the given array in hashmap.
That is all for this article, thank you for taking your time to read this. If you have any questions or doubts, please let us know in the comments section below, we will be happy to answer you.
If you found this article useful, do not forget to subscribe to our website, your support motivates us to bring out more such articles in future (scroll down to the bottom of the page to find the subscription form).
You can explore more such amazing articles from code recipe in our blogs section.
Code Recipe Limited Time Offer: Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time - Join now.
