This is probably our very first coding preparation question. The original question can found here.
This question is asking us to return the indices of 2 elements such that their sum equals to the target number.
Brute Force
The brute force way is: for each element, find its counter part in the remaining of the array elements.
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
if not nums or len(nums) < 2:
return [-1, -1]
length = len(nums)
for i in range(length - 1):
for j in range(i + 1, length):
if nums[i] + nums[j] == target:
return [i, j]
return [-1, -1]Time complexity: O(n^2). Space complexity: O(1).
Sort & 2 Pointers
There’s one chanllenge to this problem: array is not sorted and we need to return the indices of the candidates. If we sort the array, the original index is lost. So we’ll create a new array to store both the elements and their indices together:
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
if not nums or len(nums) < 2:
return [-1, -1]
nums_with_indices = [
(number, index) for index, number in enumerate(nums)
]
nums_with_indices.sort()
left, right = 0, len(nums) - 1
while left < right:
if nums_with_indices[left][0] + nums_with_indices[right][0] < target:
left += 1
elif nums_with_indices[left][0] + nums_with_indices[right][0] > target:
right -= 1
else:
return [nums_with_indices[left][1], nums_with_indices[right][1]]
return [-1, -1]Time complexity: O(nlogn). Space complexity: O(n).
Our forever friend: HashMap
When iterating through the array, the quickest way for finding its counter part is by looking it up in a hash table. We can store each element in a hash table with key as the number itself, and value is its index:
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
if not nums or len(nums) < 2:
return [-1, -1]
hashmap = {}
for index, number in enumerate(nums):
if target - number in hashmap:
return [hashmap[target - number], index]
hashmap[number] = index
return [-1, -1]Time complexity: O(n). Space complexity: O(n).