1. Two Sum

Given an array of integers nums and an integer target, return the indices of the two numbers that add up to target. Each input has exactly one solution, and you may not reuse the same element twice.

Input:  nums = [2, 7, 11, 15], target = 9
Output: [0, 1]

First Thoughts

My first approach was to check every unique pair of elements and return the pair whose sum equals the target.

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

This works because the nested loops eventually examine every possible pair. Starting the inner loop at i + 1 also prevents comparing an element with itself or checking the same pair twice.

(0,1)
(0,2)
(0,3)
...

The downside is the runtime. In the worst case, the algorithm checks roughly every pair of elements, giving it a time complexity of O(n²). It only uses a constant amount of additional memory, so its space complexity isO(1).

• Time: O(n²)
• Space: O(1)

Although this solution passes, the quadratic runtime suggests that there is probably a way to avoid repeatedly searching for the second value.

Improved Approach

For any value nums[i], the value needed to complete the pair is: target - nums[i]

So, instead of searching the rest of the array for that value each time, I can store previously seen values in a hash map. The map associates each value with its index.

For each element, I calculate its complement and check whether that complement has already been seen. If it has, I have found the solution. Otherwise, I add the current value and its index to the map.

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

        dic = {nums[0]: 0}

        for i in range(1, len(nums)):
            val = target - nums[i]

            if val in dic:
                return [dic[val], i]

            dic[nums[i]] = i

Each element is processed once, and because hash map lookup is O(1) on average.

• Time: O(n)
• Space: O(n)

This trades additional memory for a significantly better runtime, reducing the time complexity from O(n²) to O(n).