So, let's say we have an algo problem with the following statement
Given a package with a weight limit
limit
and an arrayarr
of item weights, implement a functiongetIndicesOfItemWeights
that finds two items whose sum of weights equals the weight limitlimit
. Your function should return a pair[i, j]
of the indices of the item weights, ordered such thati > j
. If such a pair doesn’t exist, return an empty array.
Problem Analysis
Before writing any code in an interview or an algorithmic problem try to explain it in plain English or pseudocode.
Parameters
- limit
- arr
Requirements
- Finding two items in arr whose sum is
limit
- 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.
Naive Solution
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
Time complexity
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.
More efficient solution
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.
Time complexity
The time complexity of this algorithm is O(n)
because we transverse the array once.
Space complexity
Hashmaps have an O(n)
space complexity because their size increase with the number of entries.
Conclusion
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 ✌🏾🧡.