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)