So, let's say we have an algo problem with the following statement

Given a package with a weight limit

`limit`

and an array`arr`

of item weights, implement a function`getIndicesOfItemWeights`

that 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.

## 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 βπΎπ§‘.

## Top comments (0)