The greedy merchant—"No one is wise from another man's woe”

Prerequisites : 🌇kth smallest element in an array

Question

The greedy merchant is on his way to his wedding with a bag of size k. He comes across a treasure trove containing items of varying values. All the items have the same size, but different values. Since his bag can only hold k items, he must select the k most valuable items from the treasure. What strategy will the merchant use?

treasure = [20, 4, 15, 10, 7]
bagSize(k) = 3

Intuition is like magic 🪄

1. Sort the treasure in order to pick the last three items.
Copy

sorted = [4,7,10,15,20]
pick last three = [10,15,20]

2. This will take the merchant much extra time, as he has to sort the entire treasure sequence. At best, he can do this in O(n*log(n)), which is more time than he has. He needs to be in the next city for his marriage to the local chief's daughter, and he can't be late, as that will anger the chief. Unfortunately, the merchant has to leave the treasure behind and continue on his journey.
3. Upon leaving the greedy merchant happened upon a wizard's hut near the treasure. He asked for help in terms of the treasure and saw a spell being cast on a bag. The wizard said to him, "Whatever you put in the bag will be sorted in either ascending or descending order" The merchant asked, "How will that help me?" The wizard replied, "No one is wise from another man's woe. You must figure it out on your own.” The merchant leaves.

4. The merchant returns to the treasures and begins adding items from the beginning.
Copy

treasure = [20, 4, 15, 10, 7]
bagSize(k) = 3

adds 20 
adds 4 
adds 7

bag = [20,15,4]

 He repeated this process for the remaining items and ended up with the three most valuable items he could carry.

5. As he begins to put things into the bag, he is surprised to see the items sorting themselves. The bag can be opened from both the top and bottom, but he can only view the items at the top and bottom. Thus, he looks at both sides.
6. On the top, he found the most valuable item he had collected, worth 20. On the bottom, he found the least valuable, worth only 4. He had to add an item worth 10 that came next, and he didn't want to take out the most valuable item with a value of 20 on top.
7. So he decided to look at the bottom and saw the number 4. Since the bag was sorted and he was at the smallest value, and 10 was more valuable than the least valuable item he had, it made sense to take out 4 and replace it with 10.
8. Out of the four options he had to choose from, he selected the three most valuable items he could carry. He was overjoyed. As he recalled the proof by induction from his logic class, he realized that if he continued with this process, he could optimize his selections. Therefore, he repeated this process for the remaining items and ended up with the three most valuable items he could carry.
9. Some choices
1. Addition 1
Copy

treasure = [20, 4, 15, 10, 7]
                        ^ Choice

bag = [20,15,4]

takes 4 out
adds 10

bag = [20,15,10]

2. Addition 2— he knows that since 7 is less than the smallest value he has, it wouldn't make sense to add it. So he would leave it and move to the next number.
Copy

treasure = [20, 4, 15, 10, 7]
                           ^ Choice
bag = [20,15,10]

leaves 7 (smaller than the already smallest he has)

bag = [20,15,10]

10. What does the structure look like when the merchant turns his bag upside down?
1. The minimum element is on top, and all other elements are smaller than the top element. This is a MIN HEAP.
11. A Counterintuitive mindset?
1. Interestingly, in the previous question kth largest/smallest in an array, we used a max heap to find the kth smallest item. However, in this question when finding the most valuable items, we use a min heap.
2. In this question, when adding a new item to the bag we want to add a new item and maximize our gains while maintaining the limits we are given (the size of the bag in this case). To accomplish this, we need to kick out the least valuable item and add the new item. To do this, we must have the least valuable item on top, which is only possible with a min-heap.
3. In the last question kth smallest element in an array. To minimize our results we had to kick out the largest items in favor of the smallest item, to kick out the largest items we needed a max heap
12. Will he be able to reach his wedding on time?
1. The complexity time of going over the treasure trove once by the merchant is O(N).
1. Adding a new item is log(k)
2. Remember the sounds that emanated from the bag as the items moved by themselves each time a new item was added or deleted. Maintaining the heap structure contributes to the time complexity, which is, fortunately, log(k) when adding an item, where k is the size of the heap.
3. Deletion, on the other hand, has a time complexity of O(1), but maintaining the order after deletion requires log(k) comparisons
2. The space complexity will be O(k)
3. This allows us to solve the problem in n * log(k) time instead of n * log(n) time. This is faster if the bag is smaller. However, we need to consider whether it will be enough time for the merchant. Let's take a look at the worst-case scenario.
4. Here is a worst-case example, but will it still make it to the wedding? Yes, he is happy and rich.— as much as a married man can be happy. Using heaps in your solutions makes for a comfortable life.
Copy

treasure = [3,2,1,4,5,6,7,8,9,10]
bag size = 3

add 3 2 1
bag = [1(top),2,3]
			 

The lowest item just added will need to go to the top will take log(k)

remove 1 
add 4

bag = [2,3,4]


remove 2
add 5

....

For each comparison, there will be one deletion and one insertion, resulting in a time complexity of log(k). Thus, the overall time complexity will be n * log(k).

13. Thanks a heap! The End.


Side note: I've also just started reading Harry Potter. Where has this been all my life?

Implementation

from heapq import heappush,heappop 
class Solution:
    def maximizeTreasure(self, treasure: List[int], k: int) -> int:

        #min heap
        bag = []
        
        for i in range(k):
            heappush(bag,treasure[i])

      
        for i in range(k,len(treasure)):
            
            topMost = bag[0]
            toAdd = treasure[i]
            
            if toAdd > topMost:
                heappop(bag)
                heappush(bag,treasure[i])

        return bag

Complexities

Time Complexity: O(n * log(k))

Space Complexity: O(k)

SandBox (code to play with on PythonTutor)