# Two Sum

Leetcode Link: https://leetcode.com/problems/two-sum/

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.

## #

Method 1: Brute ForceAs with any problem, we always start off with the brute force technique. What is the simplest way to get the answer out, without any concern about the time complexity etc.?

We can simply use 2 for-loops and find out the indices:

This will give us the right results, but such a method will be a poor solution for a huge array. Though space complexity is in constant time of `O(1)`

, with 2 for-loops we have a time complexity of `O(n2)`

.

- Time complexity:
`O(n2)`

- Space complexity:
`O(1)`

## #

Method 2: HashingTo optimise our solution, we simply use a hashtable or dictionary. We trade space for time.

We store the numbers in the array as the keys, with the indices as the corresponding values. Each time we check if a number's complement (i.e. `target - number`

) exists in the hashtable. If yes, we have found a pair! Else, we add it to the hashtable.

The code will look like this:

This has a time complexity of just `O(n)`

since we run through the list only once. A space complexity of `O(n)`

exists since we need a hashtable to store the numbers.

- Time complexity:
`O(n)`

- Space complexity:
`O(n)`

## #

Modified Question (Sorted Array)### #

Finding Just the PossibilityIf we just need to return if a particular sum can be formed from the array, and is the array is **sorted**, then we can use a 2 pointer method.

We start with 2 pointers, `i`

and `j`

, at the start and end of the array respectively. While `i < j`

, we loop to see if `arr[i] + arr[j] == sum`

. If the result is less than required sum, we increment `i`

. Else if the result is more than the required sum, we increment `j`

. Else, if it is equal, we have found a pair and we return `true`

.

- Time complexity:
`O(n)`

### #

Using Binary Search (Not recommended)If the array is already sorted, one other option is to use binary search. For every element in the array, we can find what is the required complement. Then we can use binary search to see if that number exists in the array.

However, the time complexity for this will be `O(n * logn)`

which is worse than optimal solutions above.

- Time complexity:
`O(n * logn)`