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.
Recommended Time and Space Complexity
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)