Two Sum

Problem Statement

Given an array of integers nums and an integer target, return the indices i and j such that nums[i] + nums[j] == target and i != j.

You may assume that every input has exactly one pair of indices i and j that satisfy the condition.

Return the answer with the smaller index first.

Example 1:

Input: nums = [3,4,5,6], target = 7


Output: [0,1]

Explanation: nums[0] + nums[1] == 7, so we return [0, 1].

Example 2:

Input: nums = [4,5,6], target = 10


Output: [0,2]

Example 3:

Input: nums = [5,5], target = 10


Output: [0,1]

Constraints:

  • 2 <= nums.length <= 1000
  • -10,000,000 <= nums[i] <= 10,000,000
  • -10,000,000 <= target <= 10,000,000

You should aim for a solution with O(n) time and O(n) space, where n is the size of the input array.

You should aim for a solution with O(n) time and O(n) space, where n is the size of the input array.

Hint 1

A brute force solution would be to check every pair of numbers in the array. This would be an O(n^2) solution. Can you think of a better way? Maybe in terms of mathematical equation?

Hint 2

Given, We need to find indices i and j such that i != j and nums[i] + nums[j] == target. Can you rearrange the equation and try to fix any index to iterate on?

Hint 3

We can iterate through nums with index i. Let difference = target - nums[i] and check if difference exists in the hash map as we iterate through the array, else store the current element in the hashmap with its index and continue. We use a hashmap for O(1) lookups.

Solution

Brute Force

def two_sum_brute_force(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]
    return []

Time complexity: O(n^2) Space complexity: O(1)

Sorting

def two_sum_sorting(nums: list[int], target: int) -> list[int]:
    a = []
    for i, num in enumerate(nums):
        a.append([num, i])


    a.sort()
    i, j = 0, len(nums) - 1
    while i < j:
        cur = a[i][0] + a[j][0]
        if cur == target:
            return [min(a[i][1], a[j][1]),
                    max(a[i][1], a[j][1])]
        elif cur < target:
            i += 1
        else:
            j -= 1
    return []

Time complexity: O(n \log n) Space complexity: O(n)

Hash Map (Two Pass)

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


    for i, n in enumerate(nums):
        indices[n] = i


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

Time complexity: O(n) Space complexity: O(n)

Hash Map (One Pass)

def two_sum_hash_map_one_pass(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

Time complexity: O(n) Space complexity: O(n)