## Two Sum Example and Solutions

Hi everyone, I’m back, this time with a common problem off of Leetcode.

Last week at NYC Python’s project night event we did some Leetcode
problems. There was a lot of discussion around `Two Sum`

.

`Two Sum`

is the first problem on Leetcode and is ranked as “Easy”.

The premise is the following:

Given an array of integers

`nums`

and an integer`target`

, return theindices of the two numbers such that they add up to.`target`

Let me re-explain that in my own words – we have a list, `nums`

,
and one integer called `target`

. There are two integers in `nums`

whose
sum is equal to `target`

. Retrieve the indices of those integers – not
the integers themselves.

Leetcode gives you the following starter code:

```
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
```

## Binary Search Solution

It is up to us to complete `twoSum`

with the answer, and I’ve added my
solution below, with comments:

```
from typing import List # For type annotations
class Solution:
def binary_search(self, container: List[int], key):
low = 0
high = len(container) - 1
while (low <= high):
middle = (low + high) >> 1
middle_value = container[middle]
if middle_value < key:
low = middle + 1
elif middle_value > key:
high = middle - 1
else:
return middle # This is our index.
return None # `key` wasn't found in this `container`.
def twoSum(self, nums: List[int], target: int) -> List[int]:
for index, value in enumerate(nums):
complement = target - value
complement_index = self.binary_search(nums, complement)
if complement_index is not None:
if complement_index != index:
return [index, complement_index]
return None
```

Since we were asked for indices, I went for a binary search solution
because the binary search algorithm is meant for finding the position of
our `key`

value within an array.

Binary search is meant to be run against sorted arrays according to Wikipedia. In my solution I am assuming my array is already sorted. My answer is still accepted by Leetcode, but I should’ve sorted the array.

Now to explain my answer starting from the `twoSum`

function definition:

I call

`enumerate`

against`nums`

so that I can track the index and the value on each iteration.I’m looking for the “complement” of

`target`

. So on a given iteration,`target - value`

is my complement, and I want to know if`complement`

exists in`nums`

already, here is where I call`binary_search`

to get the index.I check twice:

i. Did I get a valid index?

ii. Is that index different from the one in my current iteration?

If the above two are true, then I can return my current index and the index of the complement as a

`List[int]`

.

I could improve on my answer for better type hinting, but this is fine.

One of our regular attendees let me know that we could use a `dict`

to
do this in `O(1)`

for constant time.

## Hash Table Solution

As I shared my screen, everyone talked over one another in voice chat since this solution actually uses less lines of code:

```
from typing import List
class Solution:
def twoSum_dict(self, nums: List[int], target: int) -> List[int]:
table = dict() # This is where we store possible indices
for index, value in enumerate(nums):
complement = target - value
if value not in table:
table[complement] = index
else:
return [index, table[value]]
return []
```

There was a lot of arguing over that `if-else`

statement, some people
wanted to return first, but it doesn’t matter.

We create an empty dictionary to hold `complement`

and `index`

as our
*key-value* pairs. Then we iterate through `nums`

like before.

This time we want to know: every time we find a complement, put `value`

in `table`

if it isn’t already there. If it is there, then we know we
have a matching pair of indices.

That’s much faster than finding a complement and running binary search, which actually solves the follow up question Leetcode gives:

Follow-up:Can you come up with an algorithm that is less than `O(n^2) time complexity?

I hope you found that helpful or interesting as I did. I wanted to share because a lot of folks at project night liked talking about it. I plan to pick out another problem (likely another easy one) for this week.

Thanks for reading!