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 is the first problem on Leetcode and is ranked as “Easy”.
The premise is the following:
Given an array of integers
numsand an integer
target, return the indices of the two numbers such that they add up to
Let me re-explain that in my own words – we have a list,
and one integer called
target. There are two integers in
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
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:
numsso 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 - valueis my complement, and I want to know if
numsalready, here is where I call
binary_searchto 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
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
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
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
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!