So, let's say we have an algo problem with the following statement
Given a package with a weight limit
limitand an array
arrof item weights, implement a function
getIndicesOfItemWeightsthat finds two items whose sum of weights equals the weight limit
limit. Your function should return a pair
[i, j]of the indices of the item weights, ordered such that
i > j. If such a pair doesn’t exist, return an empty array.
Before writing any code in an interview or an algorithmic problem try to explain it in plain English or pseudocode.
- Finding two items in arr whose sum is
- Returning the indices of these items
- The bigger index should be the first in the returned array.
The basic idea is finding a pair that adds up to the limit
limit. The first solution you may think of is having a nested
for-loop where we try to find a pair that sums up to limit.
Notice how we used
for index in range(numIndex+1, len(arr)):
in the second for-loop? We don't want to compute the same pair twice, so we set the second loop to be an index ahead of the first. So for an array:
[2, 4, 1, 5], we have the following pairs
2, 4 2, 1 2, 5 4, 1 4, 5 1, 5
The implementation above has a time complexity of
O(n^2) (quadratic) because of the for-loop. In the worst case, we will have to compute the last pair before returning an answer.
We aim to reduce the time-complexity from quadratic time to linear or logarithmic time. One way to approach this is to eliminate the nested loop. This means storing the results of the computation somewhere. A hashmap will be a good data structure for this. Since we are using python, we will use a dictionary.
The idea here is to transverse the array once and find the weight's complement
limit - weight at each iteration. We check if that complement is in the array. If it is, we know we have succeeded. Remember the ultimate goal is to find a weight-complement pair that adds up to
limit. So if the complement exists in the array, we can proceed to return
- The weight's index
- The complement's index
This algorithm can be classified as a non-greedy algorithm. We try to return a result as soon as possible.
The time complexity of this algorithm is
O(n) because we transverse the array once.
Hashmaps have an
O(n) space complexity because their size increase with the number of entries.
You have learned a use case of hashmaps and how to move from a nested
for-loop to a cleaner solution using a hashmap. The hashmap uses more space but offers faster implementation. Thanks for reading. Adios ✌🏾🧡.