Two Sum problem -Leetcode #1
Tags: algorithms, interview, datastructure, leetcode
Published: 2020-12-30 22:56:14

## Two Sum

Given an array of integers **nums** and an integer **target**, return  the two numbers such that they add up to **target**.

#### First Variant (Assume only one solution)

##### *Setup*

Reading through the question - we are basically being given an array of numbers and a target number.

We need to find out two among them that add to the target , and then return them as an array.

This boils down to finding a and b such that a+b = target.

##### *Algorithms*

One way of doing this would be to loop through the numbers and adding them till we get an answer  like below

```C#
public int[] TwoSum(int[] nums, int target) {
    
        for(int aCounter=0;aCounter<nums.Length-1;aCounter++)
        {
            for(int bCounter=aCounter+1;bCounter<nums.Length;bCounter++)
            {
                if(nums[aCounter]+nums[bCounter] == target)
                    return new int[] {nums[aCounter],nums[bCounter]}; // Early Termination
            }
        }
    }
```



Imagine we have an array and a target as follows

```c#
int [] nums =[2,1,5,8,6]
target = 14
```

This would mean our result resides in the last two number

```
nums[3]+nums[4] = 14 (target)
```

Our above algorithm would go

```c#
aCounter = 0 // First Iteration
2 + 1 = 3
2 + 5 = 7
2 + 8 = 10
2 + 6 = 8
Total loops done = 4
aCounter = 1 // Second Iteration
1 + 5 = 6
1 + 8 = 9
1 + 6 = 7
Total loops done = 7 // Third Iteration
aCounter = 2
5 + 8 = 13
5 + 6 = 11
Total loops done = 9
aCounter = 3 //Fourth Iteration
8 + 6 = 14
```

As you see the answer was found in the 10 iteration - Essentially , the worst case being running the loop b (n-1-a) times to get the answer.  The worst case hence depends on the bCounter as well as the aCounter.  Complex Mathematics aside - since there is a loop within a loop - this is O(aCounter * bCounter) time complexity algorithm. We know aCounter and bCounter are same, the max of which could be n. ***This becomes an O(n<sup>2</sup>) time complexity function. We are not storing values - so this does not need extra space, it remains an O(1) space complexity function.***

However the above solution would have a non-trivial runtime if the ***nums*** array would be large . Imagine this array when it is of size *10<sup>10</sup>* and the last two numbers match. 

*Can we optimize the time complexity at the expense of space complexity?* *Is there a way for me to go over the array only once*?

```mathematica
a + b = target 
```

also means

```mathematica
 a = target - b
```

So if I have a way to **look up** past values then using the above formula, I can determine whether this satisfies the condition

Going through the Data Structures at my disposal, what data structure would do a fast lookup - a Hash based data structure eg: HashSet, Dictionary, etc.

How about we store values in the HashSet as we go through the array, and every time we reach a new value, we check if the formula above is satisfied.

```c#
public class Solution {
    public int[] TwoSum(int[] nums, int target) {
       HashSet<int> hash=  new HashSet<int>();
       for(int i =0;i<nums.Length;i++)
		{
            if(hash.Contains(target-nums[i]))
                return new int[]{target-nums[i], nums[i]};
            else
                hash.Add(nums[i]);
        }
        // If guaranteed a solution, will never hit
        return new int[0];
    }
}
```

This also only has to run through the array once.

| Hash          | Target | B     | Target-B |
| ------------- | ------ | ----- | -------- |
| {}            | 14     | 2     | 12       |
| {2}           | 14     | 1     | 13       |
| {2,1}         | 14     | 5     | 9        |
| {2,1,5}       | 14     | 8     | 6        |
| **{2,1,5,8}** | **14** | **6** | **8**    |
|               |        |       |          |

The target-B is looking for 8, Hash has 8 and the program terminates. 

***Complex Mathematics aside - we loop through once so the time complexity is O(n), however what we have now used as a resource is space to save time. We are storing now n-1 elements as we loop through n - this is basically O(n) space complexity that we loop through.***

##### *Common Mistakes*

1. **Readable variables** - if you notice , I have used <u>*aCounter*</u> in the first piece of code, while *<u>i</u>* in the second piece of code. The difference in ease of understanding can be easily seen between the two.

   ```c#
                   return new int[]{target-nums[i], nums[i]};
   ```

   ```c#
   				return new int[] {nums[aCounter],nums[bCounter]};
   ```

   

2. **Error Handling** - None of the code's handle a null nums or an empty nums. We should always sanitize the input.

   ```c#
   if(nums == null)
               return new int[0];
   ```

   

3. **Early Termination** - On a question where there is only one solution, we should use that information to terminate early. Basically that ensures that if the answer is in the first part of a long array, we are not wasting compute. Remember this does not impact the time complexity of algorithms which are generally described in Big O(worst-case).

4. **Hidden Conditions and Edge Cases** - Have a set of edge cases to work the algorithm against. Negative numbers, zero target etc.

#### Other Variants

1. Return all possible combinations that match target 

   a. Do not terminate early

2. Return indices of matched combinations 

   a. Use a Dictionary instead of a Hash Set