Standard yet An Important Question

Today I'm gonna share my views on one of the standard but important problems for interviews on LeetCode, yup! you guessed it right, the "Two Sum" problem.

Basically, we are given an array of integers named 'nums', and a variable of integer named "target". We are supposed to return indices of the two numbers from the 'nums' such that their sum equals the 'target'.

Months ago, when I solved this question for the first time, the Brute Force Approach that came to my mind was: Running two nested loops to check all possible pairs of numbers in the given array and check if the sum equals the target sum. If they reach the target sum, return the pair.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ans;
        int n=nums.size();
        for(int i=0; i<n; i++) {
            for(int j=i+1; j<n; j++) {
                if(nums[i]+nums[j]==target) {
                    ans={i, j};
                    return ans;
                }
            }
        }
        return ans;
    }
};

This can be a good solution for someone who solved the question for the first time or is a beginner, but ufff! just have a look at the time complexity, we are using two nested loops, so it will surely take O(n²).

One more optimized approach to solve this question is by using a Hashmap! We can use unordered_map to store the array elements as keys and their indices as values. By doing this, the HashMap can be used to find the complement of the current element in constant time. Hence, we can find the indices of two elements whose sum is equal to the target sum.

So, the Approach will be:

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

Create an unordered_map "map" to store the array elements as keys and their indices as values. Use a for loop to iterate through the input array. For each element, check if the 'y' (target minus the current element) exists in the unordered map. If it is present, return a vector containing the index of the current element and the index of 'y'.

This can be a Better Approach as we used the loop only once, clearly the Time Complexity will be O(n) and Space Complexity will also be O(n) as we used unordered_map.