1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

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

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Solution in Python

1. Approach 1: Brute Force

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i, a in enumerate(nums):
            diff = target - a
            for j, b in enumerate(nums[i+1:]):
                if diff == b:
                    return [i, i+1+j]

Complexity Analysis

• Time complexity : O(n²). For each element, we try to find its complement by looping through the rest of array which takes O(n). Therefore, the time complexity is O(n²).
• Space complexity: O(1).

2. Approach 2: One-pass Hash Table

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hmap = {}
        for i in range(len(nums)):
            diff = target - nums[i]
            if diff in hmap:       
                return [hmap[diff], i]
            hmap[nums[i]] = i

Complexity Analysis

• Time complexity: O(n). We traverse the list containing n elements only once. Each look up in the table costs only O(1) time.
• Space complexity : O(n). The extra space required depends on the number of items stored in the hash table, which stores at most n elements.