Daily Coding Problem Write-up

Day 1 — Two Sum

Donovan So

Jul 23, 2018·1 min read

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 = 9return [0, 1]

Bruteforce — O(n²) runtime, O(1) space

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
}

Hash Table — O(n) runtime, O(n) space

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.