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

Thanks for reading!