Two sum problem (The foundation)

NOTE - please read this article properly and solve the question twice once on paper and then on leetcode because this question serves as the foundation for the upcoming question In this category that is, 3 sum and 4 sum

Question

Click Here

Approaches

Approach one (Brute Force)

1. We need to find the pair of two digits present in the array/vector which on addition gives the sum equal to the given target.

2. So the first idea that comes to our mind is to find all the permutations and then find the sum and return the value when it is equal to the target.

3. For this task, we will use two loops, the outer loop to fix a particular digit and create the combinations with the digits present on the right of that digit and then once we get the right combination we will return the answer.

Code

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for(int i=0;i<nums.size() - 1; i++){
            for (int j = i+1; j<nums.size(); j++){
                if(nums[i]+nums[j] == target){
                    return {i,j};
                    // break;
                }
            }
        }
        return {}; // such combination doesn't exist        
    }
};

Approach two (The Optimal Approach)

1. Here to get the right pair we will use the concept of an unordered map because the time complexity of the search operation here is O(1).

2. In this approach, like we did In the first approach we will fix the first digit and since we need to find the number that will be added to the first digit to give a total sum equal to the target, we will subtract the first digit from the target and will try to find that number in the map, and if the number is not found we will insert the first digit into the map.

3. Repeat these steps until we find, the correct pair.

    class Solution {
    public:
        vector<int> twoSum(vector<int>& nums, int target) {
            unordered_map<int, int> mpp;
            int n = nums.size();
        for (int i = 0; i < n; i++) {
            int num = nums[i];
            int moreNeeded = target - num;
            if (mpp.find(moreNeeded) != mpp.end()) {
                return {mpp[moreNeeded], i};
            }
            mpp[num] = i;
        }
        return{-1,-1};
        }
    };
   

All the best for your DSA journey! Let me know your feedback so that we can improve this article together.

Ujjwal Sharma