Hey all! This is going to be my first article here in my new blog! I hope you like it! But before starting, let's clear the "why" part. So, In my college, at the end of every academic year, we have to submit a few activities that we did throughout the year to get something called MAR points which is like a mandatory thing to get the degree. One of those activities is publishing a coding solution online. And I did post some solutions in my other articles in DEV, I want to use this as an excuse to open a blog with hashnode because I wanted to try this out for a long time! And today is the last day for submission of this article so I need to hurry! Let's get started.

The Problem

The problem we will be seeing today is literally the easiest problem on leetcode. Its called Two Sum. Here's the problem statement.

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.

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.

Solution

Now, before writing down the solution that I would like to show you, let's quickly skim through some other solutions as well.

• Brute Force In this approach, we pick an element(a) and loop through every other element(b) and check if a + b is equal to the required sum or not. So that's two loops.

Time Complexity: O(n^2) Space Complexity: O(1)

• Hash Table With 2 Loops In this approach, We loop through the array once and we add each element's value as a key and its index as a value to the hash table. And then in the next loop, we check if the difference between the current element and the required sum exists in the hash table. If there is such a value present we get its index from the hash table, otherwise nothing. So that's two loops but one by one.

Time Complexity: O(n) Space Complexity: O(n) [for extra array]

Final Solution: Hash Table with 1 Loop

This approach is similar to the previous one, except in this one we check if the difference between the current element and the required sum exists in the hash table in the same loop where we store the values in it. So, store the current element in the hash table and check the hash table in the same loop and repeat this n times where n is the number of elements in the array.

Time Complexity: O(n) Space Complexity: O(n)

So no theoretical improvement in terms of complexity but we are actually reducing the number of loops that we have to run.

Code

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // hash table where we add each element's value as a key and its index as a value
        map<int,int> hash_map;

        // loop through the array
        for (int i = 0; i < nums.size(); i++) {   
             // check if the difference between the current element and the required sum exists in the hash table    
            auto complement = hash_map.find(target - nums[i]);
            if (complement != hash_map.end()) {
                // no such pairs found
                return {complement->second, i};
            } else {
                // value as a key and its index as a value
                hash_map[nums[i]] = i;
            }
        }     
        // pair found   
        return {-1,-1};
    }
};

Done! I wrote this in a bit of a hurry. Please do let me know if there are any mistakes. Would love your feedback! Also, more interesting articles coming your way soon. Stay tuned! See you in another article!