# Osi on Tech # Algorithmic walkthrough: Merging 2 Packages

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.

1. limit
2. arr

### Requirements

1. Finding two items in arr whose sum is `limit`
2. Returning the indices of these items
3. 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

1. The weight's index
2. 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 ✌🏾🧡.