[LC] 1. Two Sum

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

Question

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Thoughts

There is probably a bunch of solution since it is a most famous problem in LC. First, I may compare every two pairs like brute force. For example, loop 1 will select one number indexed by i, and the inner loop will cover another one number indexed by j and i!=j. Then we can compare nums[i] +nums[j] = target. In that case, the time complexity is $latex O(N^2)$ So, it’s not a good idea.

Another solution can be made by a two-pointer. We can first sort array and have a two-pointer i=num[0] and j=num[n]. Then we can compare num[i]+num[j]. Let says the sum of them is k, then we should find k == target. If k is less than a target, we increase i since num[i] is the smallest number so far. If k is larger than a target, we decrease j since num[j] is the largest number. Likewise, we keep continuing this procedure until i >= j. In that case, the time complexity is O(NlogN) since we need sorting.

Can we do more better? Maybe there is a single loop solution if we loop the array in a constant N time. We know that in the sense of Big-O notation, 2N or 3N all those are the same as O(N). So, maybe we can use this character. Then, let’s think about a + b = target. How about we first calculate some information, store it, and use it for the next calculation? a + b = target means a = target – b. So, first, we can save all target – b in map[target-b], and in the next loop we can simply check whether there is a map[a] or not since target – b = a.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # a + b = target, a = target - b
        # first insert all target - b in map valued as index no
        # second, find if a exist in b if not equal index
        
        d = collections.defaultdict(int)
        for i, num in enumerate(nums):
            d[target - num] = i
            
        for i, num in enumerate(nums):
            if num in d and d[num] != i:
                return [i, d[num]]
        return []

Submission

Runtime: 52 ms, faster than 26.98% of Python3 online submissions for Two Sum.Memory Usage: 14.6 MB, less than 13.36% of Python3 online submissions for Two Sum.

In this case, both time and space complexity is O(N)