Algorithm and Data Structure (Two Number)

Two Number

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
There can be duplicate elements in the array of integers. If your solutions have one of this element than consider the position of the first element.
If no such elements exist then return [-1,-1].

Given input = [1, 3, 6, 8, 2], target = 10,

Because input [3] + input [4] = 8 + 2 = 10,
Output : [3, 4].

Do not use the element with same position twice.
e.g input = [2, 7, 2, 8, 6], target = 4
Output =[0,2] is correct, where index 0 and 2 both has element 2 but in different position.
Output= [0,0] is wrong. Here we are repeating the element with the same position.

Method 1 (Brute Force):

We can use brute force approach to solve this problem. We take each element and add with
other elements in the array and check if their sum is equal to the target value.
If we have such sum than we break from the loop and return the positions in the array.

Implementation(c#) :

     public int[] TwoSum(int[] input, int target)
        {
        
              for(int i=0;i<n-1;i++)
                {
                     for(int j=i+1;j<n;j++)
                       {
                          if(input[i]+input[j] == target)
                           return new int[]{i,j};
                        }
                }
               return new int[]{-1,-1};
         }

Time Complexity is O(n-1) * O(n) = O(n^2).
Space Complexity is O(1).

Method 2 (Sorting): First we can sort the array using MergeSort which has the time complexity of      O(n Log n) in all best, worst and average case.
After sorting we will run a loop  and find pair of elements as shown below :

      if input[i]+ input[n-1] == target , n is the length if the array.
        a = input[i];
        b = input[n-1]

     if input[i]+ input[n-1] > target
        n--;

     else
        i++

Input = [1, 3, 6, 8, 2 ], target = 10

After Sorting : [1,2,3,6,8], i=0, n=5
Now check if input[i]+input[n-1]
i.e 1+8=9<10 so increase I
      2+8 =10 so assign 2 and 8 to some temporary variable;

Now try to find their actual position in the original unsorted input array and return their actual positions in sorted order.

Remember to keep a copy of the original input.

Time Complexity =  O(n log n)
Space Complexity = O(n) + O(n) +2C = O(2n)

Implementation

public int[] TwoSum(int[] nums, int target)
        {
            var nums1 = (int[])nums.Clone(); // copy of original input
            var result = new int[2]{-1,-1};
            Array.Sort(nums);
            int a = 0, b = 0;
            int n = nums.Count();
            int i = 0;
            while (i < n)
            {
                if (nums[i] + nums[n - 1] == target)
                {
                    a = nums[i];
                    b = nums[n - 1];
                    break;
                }
                else if (nums[i] + nums[n - 1] > target)
                    n--;
                else
                    i++;
            }
            int apos = -1, bpos = -1;
            i = 0;
             n = nums.Count();
            while (i < n)
            {
                if (apos == -1 && a == nums1[i])
                {
                    apos = i;
                    i++;
                }
                  
                if (bpos == -1 && b == nums1[i])
                    bpos = i;
                if (apos != -1 && bpos != -1)
                    break;
                i++;
            }
            if (apos <= bpos)
            {
                result[0] = apos;
                result[1] = bpos;
            }
            else
            {
                result[1] = apos;
                result[0] = bpos;
            }  
          
            return result;
        }

Method 3 (Hash Table) :

Using the hash table to solve this problem will be the best approach.
Here we will create a hash table with a key as the number and its index as the value in the input array.
Then check if the target- input[i] is present in the table or not.

E.g target = 10, input[i] starting from 1 in array [1,3,6,8,2]
                                                                                                   hashtable(number,position)
check 10-1 =9 is in hastable, if no than add 1 in table                    1,0                    

check 10-3 = 7 is in a hashtable if no then add 3 in table               3,1

check 10-6 = 4 is in the hash table if no then add 6 in table           6,2

check 10-8 = 2 is in the hash table if no then add 8 in table           8,3

check 10-2 = 8 is in the hashtable, if yes then return i and value of key 8 from a table.

i.e index of 2 is 4 and  index of 8 is 3 so return [3,4]

Remember: If there are any duplicate numbers than do not add in the hash table as it will not support.
*If the problem would have been to find only pairs, not their position than we could have used the only hash set instead of the hash table.

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

Implementation :

public int[] TwoSum(int[] nums, int target)
        {
            int[] result = new int[2]{-1, -1};
            var map = new Dictionary<int, int>();
            for (int i = 0; i < nums.Count(); i++)
            {
                if (map.ContainsKey(target - nums[i]))
                {
                    result[1] = i;
                    result[0] = map[(target - nums[i])];
                    return result;
                }
                if(!map.ContainsKey(nums[i])) // add only if its not present
                map.Add(nums[i], i);
            }
           return result;
        }