# Get Free Delivery from Amazon

To implement this feature, we will have access to a list of products that the customer is likely to buy. These products will include the items from their wishlist and other items based on previous purchases. We will also be given the amount, n, that the customer needs to spend in addition to the current total: n=[free shipping price−current total].

Let’s say you are given a list of numbers containing the prices of products that a customer is likely to buy, `{2, 30, 56, 34, 55, 10, 11, 20, 15, 60, 45, 39, 51}`. In addition, the amount that needs to be spent to claim the free delivery offer is `61` dollars. Then, we can see that the sum of `10` and `51` is `61`. Therefore, we will suggest the customer buys these products. Our program should return the indices of these products in an array such as: `{5, 12}`.

You can assume that the list contains at least one pair of products to suggest. If there is more than one pair, you can suggest any of them.

The following illustration shows how products are mapped to prices for the example we are discussing. The prices have been rounded off for simplicity.

The illustration given below shows how we obtained the result from the list of prices.

## One-pass Hash Table

Algorithm

It turns out we can do it in one pass. While we are iterating and inserting elements into the hash table, we also look back to check if the current element’s complement already exists in the hash table. If it exists, we have found a solution and return the indices immediately.

Implementation

Complexity Analysis

• Time complexity: O(n). We traverse the list containing n elements only once. Each lookup in the table costs only O(1) time.
• Space complexity: O(n). The extra space required depends on the number of items stored in the hash table, which stores at most n elements.

Full Stack Programmer, love to solve problem’s during free time.

## More from Jaydeep

Full Stack Programmer, love to solve problem’s during free time.