Two Sum 🧠
LeetCode Link: Two Sum
Difficulty: Easy
Problem Explanation 📝
Problem: LeetCode 1 - Two Sum
Description: Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
Intuition: To find the pair of numbers that add up to the target, we can utilize a hash map. By iterating through the array and checking if the complement (target - current number) exists in the hash map, we can efficiently find the desired pair.
Approach:
- Initialize an empty hash map to store the elements and their indices.
- Iterate through each element num and its index in the input array nums:
- Calculate the complement as target - num.
- If the complement exists in the hash map, return the indices [map[complement], index].
- Otherwise, add the current element num and its index to the hash map.
- If no solution is found, return an empty vector or handle it as per the problem's requirement.
⌛ Time Complexity: The time complexity of this approach is O(n), where n is the size of the input array nums. This is because we iterate through the array once and perform constant-time operations for each element.
💾 Space Complexity: The space complexity is O(n), as the hash map can potentially store all elements of the input array.
Solutions 💡
Cpp 💻
class Solution {
public:
vector<int> twoSum(vector<int> &nums, int target) {
unordered_map<int, int> numMap;
for (int i = 0; i < nums.size(); i++) {
int complement = target - nums[i];
if (numMap.count(complement) > 0) {
return {numMap[complement], i};
}
numMap[nums[i]] = i;
}
return {}; // Handle no solution as per problem's requirement
}
};
// class Solution {
// public:
// vector<int> twoSum(vector<int>& nums, int target) {
// unordered_map<int, int> M;
// vector<int> res;
// for(int i = 0; i < nums.size(); i++) {
// int compliment = target - nums[i];
// // If we find the compliment
// if(M.find(compliment) != M.end()) {
// // returning i and index of compliment
// res.push_back(M[compliment]);
// res.push_back(i);
// }
// else // insert pair
// M.insert( {nums[i], i});
// }
// return res;
// }
// };
Python 🐍
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
prevMap = {} # val -> index
for i, n in enumerate(nums):
diff = target - n
if diff in prevMap:
return [prevMap[diff], i]
prevMap[n] = i