Problem Statement

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.

Additional information

• The array will contain at least 2 elements.
• Only one valid answer exists.
• The function should return the indices, not the values.

Example 1:

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

Output: [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]

Brute Force

Intuition

The most straightforward method is to check every combination of two numbers in the array to see if they sum up to the target. We iterate through each element x and try to find another element y such that x + y = target.

Algorithm

1. Iterate through the array with a loop variable i from 0 to n-1.
2. Iterate through the remaining elements with a loop variable j from i + 1 to n-1.
3. Check if nums[i] + nums[j] equals target.
4. If it does, return [i, j].

def two_sum(nums: list[int], target: int) -> list[int]:
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

Time & Space Complexity

• Time complexity: O(n^2)
• Reason: For each element, we try to find its complement by looping through the rest of the array, resulting in a quadratic runtime.
• Space complexity: O(1)
• Reason: We only use two variables for the loops and do not store any extra data structures.

One-Pass Hash Map

Intuition

To improve efficiency, we can check if the "complement" (the number needed to reach the target) exists in the array as we iterate. A Hash Map is perfect for this because it allows us to look up values in O(1) time. As we visit each number, we check if target - num is already in our map.

Algorithm

1. Initialize an empty dictionary prevMap to store the mapping of value -> index.
2. Iterate through the array nums with index i and value n.
3. Calculate diff = target - n.
4. Check if diff exists in prevMap.

• If yes, return [prevMap[diff], i].
• If no, add the current number to the map: prevMap[n] = i.

def two_sum(nums: list[int], target: int) -> list[int]:
    prev_map = {}  # val : index

    for i, n in enumerate(nums):
        diff = target - n
        if diff in prev_map:
            return [prev_map[diff], i]
        prev_map[n] = i
    return []

Time & Space Complexity

• Time complexity: O(n)
• Reason: We traverse the list containing n elements exactly once. Each lookup in the table costs O(1) on average.
• Space complexity: O(n)
• Reason: In the worst case, we might store all n elements in the hash map.