Two Sum

Two Sum

Question:

Given an array of integers ‘nums’ and an integer ‘target’, return indices of two integers in the array that sums up to target.

You may assume that there is exactly one answer, may not use the same index twice, and the order of indices does not matter.

My Line of Thought:

I first thought of the most intuitive, brute force way to solve this question, which is simply iterating through all the numbers in array using two for-loops. That solution was too slow, O(n^2) complexity due to the for-loop within a for-loop, so I needed to speed things up.

Then, I thought that I could make my solution more efficient by making the searching of the index O(1) using a Hashmap. With an appropriate hash function, one that does not make many collisons, the searching of the index given a value will only take O(1) complexity. Therefore, I initialized a hashmap with keys as the numbers in the array ‘nums’ and values as the indices of those numbers.

While I could use a for-loop to put all the numbers in the hash map, then check if the difference between the ‘target’ and the ‘number’ exists, I believe that I could do this while checking. It will be slightly faster since, I would be only iterating through the for-loop once.

My Implementation:

class Solution(object):
    def twoSum(self, nums, target):
        hashmap = {}
        for i in range(len(nums)):
            complement = target - nums[i]
            if complement in hashmap:
                return[i, hashmap[complement]]
            hashmap[nums[i]] = i
        # for i, items in enumerate(nums):
        #     complement = target - items
        #     if complement in hashmap:
        #         return [i,hashmap[complement]]
        #     hashmap[items] = i

Reflection:

I did not think solving this simple question will make me think this much, but just to ramble on…

After submitting, there was a dispute over whether to use a len(nums) in the for-loop or use function enumerate(). In terms of efficiency, using enumerate() function creates an enumerate object which one by one yields a result, which you might think will be faster than iterating using len(nums). However, my solution will immediately return the indices as soon as they find the combination that sums up to target. Threrfore, there was basically no difference between the two in terms of efficiency, but using enumerate() will take up more memory.

I submitted solution using len(nums), because Leetcode will evaluate in terms of time and memory efficiecy.

With more digging on the web, using enumerate function is one of the ways to make my code more “Pythonic.”

What does “Pythonic” even mean? How is that coding style leveraging Python’s unique features to make my code more “beautiful and readible?”

I was very intrigued by these questions, so I decided to pick up a book called ‘Effective Python’ while solving these Leetcode questions!