Two Sum Problem

Two Sum Problem 

A bit of diversion today. I am going to solve the Two-Sum problem. 

Question:(You can find it in leetcode). The problem statement is shown below:

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

My approach:

• We need some way to store  the indexes of the values which sums up to target. 
• Track the sum of 2 numbers and check if the sum is equal to target.

Brute-Force Approach:

• Loop through the array to check if the sum of 2 numbers is equal to target. 

        public static int[] CalculateTwoSum(int[] arr, int d)
        {
            
            for (int i = 0; i < arr.Length; i++)
            {
                for (int j = i + 1; j < arr.Length; j++)
                {
                    if (arr[i] + arr[j] == d)
                    {
                        return new int[] { i, j };
                    }
                }
            }

            return new int[] { };
        }

Time Complexity: 

The above code will run

• At the max "N" Times in i Loop
• At the max "N" Times in j Loop 
• This leads us to N*N = N² 
• Time Complexity is O(N²);

Faster Approach:

A faster approach is available where we can make use of Dictionary or Hashtable

• Calculate the difference of Target and Array value
• If the difference is present in the dictionary, then we return the index of the values.
• If the difference is not present in the dictionary, we add the array value to the dictionary.

     

        public static int[] CalculateTwoSumFaster(int[] arr, int target)
        {
            //Initialize a new Dictionary Object.
            Dictionary dictionaryOfIndexes = new Dictionary();

            // Loop through Every array.
            for(int i=0;i            {
                //Calculate the difference of the Target and Array Value.
                int diff = target - arr[i];

                //If the dictionary has the Key value of Difference, then we found 
                //a match, return the  indexes.
                if(dictionaryOfIndexes.ContainsKey(diff))
                {
                    return new int[] { dictionaryOfIndexes[diff], i };
                }
                // else we add the array value and it's index accordingly.
                else if(!dictionaryOfIndexes.ContainsKey(diff))
                {
                    dictionaryOfIndexes.Add(arr[i], i);
                }
            }

            return new int[] { };
        }

Time Complexity:

• This approach uses only one for Loop - Runs at the max N Times.
• Dictionary Object takes O(1) time to insert. 
• Time Complexity for the above solution is O(n);
• Space Complexity is O(1);