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 the indices 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:

1. I call `enumerate` against `nums` so that I can track the index and the value on each iteration.

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

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