Two Sum ( leetcode - 01 )
Here I will show the brute force and the optimized solution for this problem.
Problem Statement: Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to target.
You may assume that each input will have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
Brute-force Solution
Just execute two For loops, the first loop will traverse the array, and the second loop will start with (i+1) to find a number that, when added with nums[I], equals the target. When found, push their indexes into the answer vector and return it.
TC - O(N^2), SC - O(1)
C++/CPP Code-
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> ans;
for(int i=0; i<nums.size(); i++) {
for(int j=i+1; j < nums.size(); j++ ) {
if(( nums[i] + nums[j] ) == target) {
ans.push_back(i);
ans.push_back(j);
break;
}
}
}
return ans;
}
};
Optimized Solution
To optimize the above solution, we will be storing the pair [value, index] in a hash table. We will travel through the nums array, and check if target-nums[i] is present in the hash table or not; if present, we will store the indexes in the ans vector; otherwise, we will push the current element with its index into the hash table. The TC of inserting and finding an element in a hash table is O(1).
TC - O(N), SC - O(N)
C++/CPP Code-
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> ans;
unordered_map<int, int> map; //hash table
for(int i=0; i<nums.size(); i++) {
if(map.find(target - nums[i]) != map.end() ) {
ans.push_back(map[target-nums[i]]);
ans.push_back(i);
break;
}
map[nums[i]] = i;
}
return ans;
}
};