Hello! It's been a while since I've posted any articles/blogs, since I've been busy finishing up a coding boot camp with a school called devCodeCamp. Ideally, I would of wrote about what I learned along the way, however; having other responsibilities in life just got in the way, plus a coding bootcamp demands a lot of time and effort. I decided this morning to look at problems in the ever so famous algo app called LeetCode.
LeetCode Two Sum
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: 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]
Constraints:
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.
Solution 1 - Brute Force
Brute Force Algorithms are exactly what they sound like – straightforward methods of solving a problem that rely on sheer computing power and trying every possibility rather than advanced techniques to improve efficiency.
JavaScript
const nums = [2,7,11,15]
const target = 9
const twoSum = function(nums, target) {
for(let i=0; i < nums.length; i++){
for(let j = i+1; j < nums.length; j++){
if (nums[i] + nums[j] === target){
return [i, j]
}else{
continue
}
}
}
}
console.log(twoSum(nums, target)
Python
nums = [2,7,11,15]
target = 9
def twoSum(nums, target):
for i, a in enumerate(nums, start=0):
for j, b in enumerate(nums[i+1:], start=0):
if a+b==target:
return [i, j+i+1]
print(twoSum(nums, target)
Solution 2 - two pass hash map solution
JavaScript
const nums = [2,7,11,15]
const target = 9
const twoSum = (nums, target) =>{
let hashMap = {}
for(let i=0; i < nums.length; i++){
hashMap[nums[i]] = i
}
for(let i=0; i < nums.length; i++){
let compliment = target - nums[i]
if(hashMap[compliment] && hashMap[compliment] !== i){
return [i, hashMap[compliment]]
}
}
}
Python
nums = [2,7,11,15]
target = 9
def twoSum(nums, target):
hashMap = {}
for index in range(len(nums)):
hashMap[nums[index]] = index
print(hashMap)
for index in range(len(nums)):
compliment = target - nums[index]
print(compliment)
if compliment in hashMap and hashMap[compliment] != index:
return [index, hashMap[compliment]]
Solution 3 - one pass hash map solution
JavaScript
const nums = [2,7,11,15]
const target = 9
const twoSum = (nums, target) =>{
let hashMap = {}
for(let i=0; i < nums.length; i++){
let compliment = target - nums[i]
if(compliment in hashMap){
return [i, hashMap[compliment]]
}
hashMap[nums[i]]=i
}
}
const twoSum = (nums, target) =>{
let storage = {}
for(let[index, num] of nums.entries()){
if(storage[num] !== undefined) return [storage[num], index]
storage[target - num] = index
}
}
Python
def twoSum(nums, target):
hashMap = {}
for index in range(len(nums)):
compliment = target - nums[index]
if compliment in hashMap:
return [index, hashMap[compliment]]
hashMap[nums[index]]=index
