The Problem: Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to the target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [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]
The Solution:
When solving this kind of problem we have multiple ways of handling this and the first solution that comes to mind is:
1. The Brute-force solution:
This is the first idea that comes to mind when solving this challenge. The pseudocode of such a problem looks something like this:
for each number i in the list of numbers:
for each number j in the list of numbers starting from i:
if i+j equal target number, return indices
The issue with this is that you will get a worst-case runtime of O(n²). If we are searching for the two numbers we have to go to the end of the list, this will make us go through all the numbers multiple times, once in the i loop and each respective time In the j loop. This is how the code will look like for the above solution.
def twoSums(self, 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]
We need to come up with an optimal solution that will reduce the time complexity, After some thinking, we will use a Hash Table for this solution which has a quick value lookup.
Hash Table Solution:
Our thought process will be:
instantiate an empty dictionary
for each number in the list of numbers:
result = subtract the number from the target number
look for result in the dictionary
if found:
return index of number and index of dictionary result
Compared to the first example the key-value map requires only one iteration of the number list meaning we will get a runtime of O(n) which is significantly better than the Brute Force approach.
def twoSum(self, nums: List[int], target: int) -> List[int]:
dictionary = {}
answer = []
for i in range(len(nums)):
secondNumber = target-nums[i]
if(secondNumber in dictionary.keys()):
secondIndex = nums.index(secondNumber)
if(i != secondIndex):
return sorted([i, secondIndex])
dictionary.update({nums[i]: i})