Posted on

# Two Sum problem -Leetcode #1

## 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

``````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

``````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

``````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(n2) 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 1010 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?

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

also means

`````` 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.

``````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
}
// 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 aCounter in the first piece of code, while i in the second piece of code. The difference in ease of understanding can be easily seen between the two.
``````                   return new int[]{target-nums[i], nums[i]};
``````
``````                return new int[] {nums[aCounter],nums[bCounter]};
``````
1. Error Handling - None of the code's handle a null nums or an empty nums. We should always sanitize the input.
``````   if(nums == null)
return new int[0];
``````
1. 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).

2. 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

1. Return indices of matched combinations

a. Use a Dictionary instead of a Hash Set