Two Sum

Problem: leetcode.com/problems/two-sum

Naive Solution: In this approach, you iterate over every element to generate the remainder and then again iterate over all the elements to find that remainder in the list.

vector<int> twoSumExpensive(vector<int>& nums, int target) {
        vector<int> mp;
        for (int i = 0; i < nums.size(); i++) {
            int rem = target - nums[i];
            for (int j = i+1; j < nums.size(); j++) {
                if (nums[j] == rem)  {
                    mp.push_back(i);
                    mp.push_back(j);
                    return mp;
                }
            }
        }
        return mp;
    }

Better Solution: In this approach first you try to find the remainder in the map. Clearly it will not be available in the first iteration so in that case, we just create a dictionary of the element and their index.

The solution will work after the first iteration. As in the following iterations, it will be able to find out the remainder in the map.

vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ans;
        unordered_map<int, int> mapp;
        for (int i = 0; i < nums.size(); i++) {
            if (mapp.find(target - nums[i]) != mapp.end()) {
                ans.push_back(mapp[target - nums[i]]);
                ans.push_back(i);
                return ans;
            } else {
                mapp[nums[i]] = i;
            }
        }
        return ans;
    }

Join me on Twitter @ThatJsDev

Image resources

Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to the target.