1. Two Sum

Problem

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.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

• 2 <= nums.length <= 105
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Only one valid answer exists.

Discussion

Trial 1

One can easily see a trivial solution with brutal force. We loop through each element x in the list, and loop through each element again to check of target - x. Yet this is a very slow solution giving time complexity O(n^2).

Trial 2

Based on Trial 1, we can enhance the solution by preparing a hash map (dict in python). Hence we loop through each element x in the list, and check for element target - x in the hash map. As look up in hash map is atomic, the time complexity of the algorithm improved to O(n). While the hash map takes space of O(n). We sacrifice memory for algorithm performance.

Solution

Further improving trail 2, we can preparing the hash map while looping through each element in the list. For cases where no correct pair is found, we add the new element to the hash map as: {element: index} in each iteration.

Although the time complexity and space complexity remains unchanged, but for normal cases, the correct pair is found before looping through every element, so the actual iteration and size of map is smaller than n.

from typing import List

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        cache = {}

        for i in range(len(nums)):
            diff = target - nums[i]

            if diff in cache and cache.get(diff) is not i:
                return [
                    min(i, cache.get(diff)),
                    max(i, cache.get(diff)),
                ]

            else:
                cache.update({
                    nums[i]: i
                })

Complexity Analysis

• Time Complexity: O(n), as only one looping of the input list is required.
• Space Complexity: O(n), as a hash map of the elements in input array is created.