Leetcode 0001. Two Sum

Problem statement

https://leetcode.com/problems/two-sum

Solution

I think there is not a lot I can add to this very classical problem: it is the first one on leetcode, so people who just start their journey on leetcode most probably solved it.

The idea is to keep numbers in hash table and then for each number num, check if number T - num also in our hash table.

Complexity

Time complexity is O(n): we need to iterate over all numbers. However space complexity is O(n) as well to support our hash table. It is often the case when we try to decrease time complexity we need to increase space complexity, this is called time-space complexity trade-off.

Code

class Solution:
    def twoSum(self, nums, T):
        d = {}
        for i, num in enumerate(nums):
            cand = T - num
            if cand in d:
                return [i, d[cand]]
            else:
                d[num] = i