Daily Coding Problem Write-up

Given an array of integers, return indices of the two numbers such that they add up to a specific target. For example,

nums = [2, 7, 11, 15]
target = 9
return [0, 1]
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> result;
for(int j=1; j < nums.size(); j++){
for(int i=0; i < j; i++){
if(nums[i] + nums[j] == target){
result.push_back(i);
result.push_back(j);
return result;
}
}
}
return result; // no results found, return empty vector
}
vector<int> twoSum(vector<int>& nums, int target) {    // maps remainder (target - current_val) to vector index (i)
// e.g. sum[7] = 1 means the number at index 1 needs a 7 in
// order to add up to the target
unordered_map<int, int> sum; vector<int> result; for(int i=0; i<nums.size(); i++){
int current_val = nums[i];
// if current_val is a key in the unordered_map
if(sum.count(current_val) > 0){
result.push_back( sum[current_val] );
result.push_back(i);
return result;
}
sum[target - current_val] = i;
}
return result; // no results found, return empty vector
}

Note:

  • unordered_map.count(key) will return 1 if key is a key in the unordered map, 0 otherwise.

Mistakes I made:

  • I assumed current_val has to be smaller or equal to target. This is only correct if all numbers are positive, otherwise we can have -3 + 3 = 0, where 3 is > 0. Always think about edge cases.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store