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 have 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 sums equals to the 'target'.

Months ago, when I solved this question for the first time, the Brute Force Approach that came in 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, it will surely take O(n²).

One more optimized approach to do this question can be using 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 indeces of two elements who's 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, checks 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 the 'y'

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

Any other better Approach coming in your mind? umm, Have you ever heard of "Two pointer Approach"? Do share your views in the Comment Section ;)

Stay Cool!

Standard yet An Important Question

Comments