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(n²) 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¹⁰ 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
                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.

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