DAY 1 - TWO SUM

Hello to anyone reading this. I am still relatively new to coding and this platform as well, so please feel free to drop any corrections/advice for me.
I am trying to do the 100 Day-Challenge of consistent coding and this is Day-1.The goal is simple. I will solve one or more than one leetcode/gfg problem a day and post what I learnt. I am confident that this will help me improve my concepts and help me be more consistent in my practice. Looking forward to a positive interaction with all of you.

DAY1 PROBLEM 1
Two Sum

Well starting off, with one of the classics. Its the infamous two sum problem of leetcode.

Let's start by understanding the question first and then let's get to the solving part.

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order

Example:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Brute Force Approach:

If you were to ask me, before being introduced to some concepts of coding, this is most likely the way I would have approached the problem. I would have checked if two numbers add up to the target and store their indexes using two for loops.

Code would have gone like:

vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ans; // stores the result
        //traversing the array
        for(int i = 0 ; i < nums.size()-1; i++)
        {
            for(int j = i+1; j < nums.size(); j++)
            { //checking conditionality
                if(nums[i] + nums[j] == target)
                {
                    ans.push_back(i);
                    ans.push_back(j);
                }
            }
        }
        return ans;
    }

Although this does pass the test cases but its time complexity is O(n^2) because we used two nested for loops. In a time constrained environment this would not be our ideal solution. Hence we will have to come up with a more suitable solution to this.

TIME COMPLEXITY O(n^2)
SPACE COMPLEXITY O(1)

Optimized Approach

We are going to use a concept of hash table. Although a beginner would not know what this is, its still relatively easy to understand.
Let's start by doing this.
We are going to traverse the array but every time I go through an element I check if I have the required difference element from the target already. If I do have one, I will return the mapped index and current iterator position.

Let's try to understand with the example.
Example:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]

First we create a map that stores the value of our index and our index.
At start we go through 2 at index 0.
We check if we have already have (9-2) = 7 in our map.
We don't have it. So we add {2,0} to our map.
Next We go to 7 at index 1.
We check if we have (9-7) =2 in our map.
We found it!. So we return (map[2],iterator index)
In this case map[2] = 0 and index = 1.
So we return {0,1}.
Here we use the concept of space time tradeoff.
We traded off space(earlier we used constant space) but here we took upon ourselves another data holding structure but we were able to reduce down the time complexity.

TIME COMPLEXITY O(n)
SPACE COMPLEXITY O(n)

Code:

    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> maps;

        for(int i= 0; i < nums.size(); i++)
        {
            if(maps.find(target-nums[i]) == maps.end())
            maps[nums[i]] = i;
            else
            return {maps[target-nums[i]],i};
        }
        return {-1, -1};

    }

This is it. Please feel free to ask any questions in the comment section.

Comments

[Paul J. Lucas]

You should pass nums as a reference to const. You are doing each look-up in the map twice: once for find, another for []. You should use insert() instead.

[Nayan Pahuja]

Other than that, I would like to ask, How would you rate the explanation on a scale of 1-5.

[Nayan Pahuja]

I see, that was very helpful. Thanks for the tip!