Hope you all are safe and making best use of Your Quarantine Period to enhance your skills. In this Post, we will cover the solution for LeetCode 2 sum problem. We will cover the full solution in C++ language.
Problem Statement:
Given an array of integers, return indices of the two numbers such that they add up to a specific target.You may assume that each input would have exactly one solution, and you may not use the same element twice.
Explanation:
In this problem, we are given an array of integers and we have to return the indices of the pair that add up to a specific number given to us.
Example 1:
INPUT:
[2,7,11,15]
9
OUTPUT:[0,1]
As the sum of integers at 0 and 1 index(2 and 7) gives us a sum of 9.
Example 2:
INPUT:
[3,7,9,10,5]
8
OUTPUT:[0,4]
Logic:
A simple method is to use a two nested loop and generate all the pairs and check for their sum. This method will have a time complexity of O(N^2) but the problem should be solved in a linear time limit.
The Efficient Approach is to use hashing. We will use a hash map and while iterating, we will check for each element y, if there exists a target-y in the map. If it exists, we will return the indices of both integers. Otherwise, We will store that element and it’s index as key and mapped value in the map. This is done to further check for that element and also get it’s index if required.
Let us look at a example for better understanding:
Array = [3,4,8,6,7]
Target = 9
Steps:
-
Create a hash map and start iterating through the Array.
-
Check for first element 3, since no value is associated with (9-3=)6 in the map so insert (3,0) in the map.
-
Check for 4 , since no value is associated with 5 so insert (4,1) in the map.
-
Check for 8, since no value is associated with 1 so insert (8,2) in the map.
-
Check for 6, this time a value associated with 3 exist so return the index of 6 and value associated with 3 which is the index of integer 3.
Output: [0, 3]
Note: We are using map to link integer with index as it given the same element does not appear twice.
C++ Code Solution:
Let's see the full solution to this problem:
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
map<int,int> m;
vector<int> v;
for(int i=0;i<nums.size();i++)
{
if(m.find(target-nums[i])!=m.end())
{
v.push_back(m[target-nums[i]]);
v.push_back(i);
return v;
}
m[nums[i]]=i;
}
return v;
}
};
Python Code Solution
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
seen = {}
for i, value in enumerate(nums):
remaining = target - nums[i]
if remaining in seen:
return [i, seen[remaining]]
seen[value] = i
Java Code Solution
public class Solution {
public int[] twoSum(int[] numbers, int target) {
HashMap<Integer,Integer> indexMap = new HashMap<Integer,Integer>();
for(int i = 0; i < numbers.length; i++){
Integer requiredNum = (Integer)(target - numbers[i]);
if(indexMap.containsKey(requiredNum)){
int toReturn[] = {indexMap.get(requiredNum), i};
return toReturn;
}
indexMap.put(numbers[i], i);
}
return null;
}
}
JavaScript Code Solution
var twoSum = function (nums, target) {
// Array to store the result
result = [];
// Map to store the difference and its index
index_map = new Map();
// Loop for each element in the array
for (let i = 0; i < nums.length; i++) {
let difference = target - nums[i];
if (index_map.has(difference)) {
result[0] = i;
result[1] = index_map.get(difference);
break;
} else {
index_map.set(nums[i], i);
}
}
return result;
};
Kotlin Code Solution
package org.redquark.tutorials.leetcode
fun twoSum(nums: IntArray, target: Int): IntArray {
// Array to store result
val result = IntArray(2)
// This map will store the difference and the corresponding index
val map: MutableMap<Int, Int> = HashMap()
// Loop through the entire array
for (i in nums.indices) {
// If we have seen the current element before
// It means we have already encountered the other number of the pair
if (map.containsKey(nums[i])) {
// Index of the current element
result[0] = i
// Index of the other element of the pair
result[1] = map[nums[i]]!!
break
} else {
// Save the difference of the target and the current element
// with the index of the current element
map[target - nums[i]] = i
}
}
return result
}
Conclusion
This is it, we have solved the Leetcode Two Sum problem in C++, Java, Python, JavaScript, and Kotlin. I hope you liked it!!
THANKS FOR READING!
If you have any doubt, please let us know by posting in comments.
You may also like:
