Question from leet code but with my personal explanation.
I will be using python for this question.
My first approach was using 2 for loops and brute forcing this. It works for 1 case, but it exceeded time limit for the very long cases.
The above code runs in time complexity of O(n²) due to the 2 for loops. It’s doable but as the size of the array get’s larger, the time complexity also grows quadratically. Just a side note, the same double for loop approach can run finish in javascript but not python.
I then came across a solution posted by one user, which uses enumerate and a hash table. Enumerate is python specific way of calling a single for loop but with indices attached to the outcome. As for hash table, python implements it by default as a dictionary object hence no set up code was needed for that part.
This implementation ran with a promising result, using only 60ms. Since the look up for dictionary is in constant time, which is O(1), we only need to care about the for loop, which is O(n). Hence overall, the time complexity is O(n).
Now let’s break down the code bit by bit to understand more.
1. initialize d as a dictionary.
2. enumerate over arr. for each cycle, we will get a value n, which is target-num. num here refers to temporary for loop variable assigned and is equal to the element in the list (arr) we passed in.
3. check if n is in d, the dictionary. if it is not in, we will insert num as key and i as value into the dictionary. i here is the index of the arr element.
But why this logic? The key to understanding this is the use of n. An example would illustrate this well. Say my target is 11 and my array is [1,2,3,4,5,6]. We know that 5+6=11. 11–6 = 5. if you were to find 5 in the table, it means it must have came from the arr, hence my current number + (target-current number) must equal to target. Since it is a dictionary object, we just do a constant time look up to find the value of the key, which is also the index in the arr object.
I hope this is clear. Let’s code on!
