# Spike - Gio, Cam, Joe & Het ---  Look at Grammy's pearls! --- # Presentation :frog: - The two sum problem - Brute force - How data structures can help us reduce the time complexity - What we learned today --- ### Things to note before we start :frog: - Every line of code has a big O complexity - We refer to the big O in terms of the complexity of the highest order or least efficient - This is because each order of complexity is so much bigger than the lesser one the lesser one is negligible - Big Ω notation describes the best case scenario. Ω may be more valuable when the algorithim's worst case is very unlikely. --- - Every variable has a space complexity - N.B integers always take up the same amount of space - Space complexity seems to come second to time complexity but they are usually interconnected ---  --- ### The Two Sum Problem :bear: Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution, and you may not use the same element twice. --- ``` Example: Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1]. ``` --- ### What NOT to do #### Brute (Bruce) Force Solution :whale: A common solution would be to use two for loops ```javascript=1 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] } } } return [] }; ``` ---  --- ### A slightly different variation of what also NOT to do :whale: ```javascript=1 var twoSum = function(nums, target) { for (let i = 0; i < nums.length; i++) { let required = target - nums[i]; let j = nums.indexOf(required) if (j > -1 && j !== i) return [i,j] } }; ``` --- - Filing cabinet :whale:  --- ### Why does it matter? :frog: - O(n^2) Exponential - for each iteration of the first loop (potential length n), another loop of potential length n takes place - It doesn't matter too much when dealing with small inputs but beyond that it is very beneficial to increase the efficiency of our code ---- - Compare O(n^2) with O(n): - Array of 3: 9 vs. 3 = not so bad - Array of 100: 10,000 vs. 100 = pretty bad huh? --- ### The good stuff - what to do: :pig: ```javascript=1 var twoSum = function(nums, target) { let obj = {}; for (let i = 0; i < nums.length; i++) { let required = target - nums[i]; if (obj[required]) return [i, obj[required]]; else obj[nums[i]] = i; }; }; eg twoSum([1,2,3,4,5,6], 10) = [5, 3] obj = {1:0, 2:1, 3:2, 4:3, 5:4, 6:5} ``` obj pair = (arrayValue: arrayIndex) --- ### :pig: for nums array values 1-5, stores values as keys with indexes as values for num array value 6, searches object for a key of 4, returns value which is nums index. --- ### Why do dat? :bear: - We now have a for loop and a hash table - Worst case a hash table has time complexity of O(n) - We now only need one for loop with a time complexity of O(n) - Changed time complexity from O(n^2) to O(n). --- ### How do hash tables help us? :bear:  --- - The location in the table is generated based on the value (given a hash). - Given that value again, you can calculate the same hash as before. Based on the hash, we know where to look in the table - So you don't need to loop through the whole thing like an array --- ## Questions?  --- ## Resources - [Hash table - why is it faster than arrays?](https://stackoverflow.com/questions/12020984/hash-table-why-is-it-faster-than-arrays) - [leet code two sum](https://leetcode.com/problems/two-sum/)