Streaming Solution Explained | No Sorting | O(N log k)
Intuition\nThe most important thing that matters is the advantage r_1[i]-r_2[i] (the difference of rewards for mouse 1 and 2 respectively). We want to give mous
# Intuition\nThe most important thing that matters is the advantage $$r_1[i]-r_2[i]$$ (the difference of rewards for mouse 1 and 2 respectively). We want to give mouse 1 the cheese whenever it has the greatest advantage and mouse 2 the cheese whenever it has greatest advantage. \n\n# Sorting Solution\n\nOne way to do this would be by sorting and giving mouse 1 the $$k$$ cheeses where it has the greatest advantage and mouse 2 the remaining cheese:\n```\nclass Solution:\n    def miceAndCheese(self, r1: List[int], r2: List[int], k: int) -> int:\n        adv = [(x-y,y) for x,y in zip(r1,r2)]\n        adv.sort(reverse=True)\n        r1 = sum(d+y for d,y in adv[:k])\n        r2 = sum(y for _,y in adv[k:])\n        return r1 + r2\n```\n\n##### Complexity of Sorting Solution\n- Time complexity: $$O(N \\log N)$$ \n- Space complexity: $$O(N)$$\n\n##### Drawbacks of Sorting Solution\nWe have to see all the data at least once before we can do anything. Additionally, the complexity is independent of $$k$$. As we shall see, we can improve both space and time complexity if we allow ourselves to take into account $$k$$ by using heaps.\n\n# Heap Solution (No Sorting)\n\nMouse 1 only needs the $$k$$ cheeses where it has the largest advantage. Let\'s exploit this. \n\nLet\'s build a min-heap where items are sorted by mouse 1\'s advantage $$r_1[i]-r_2[i]$$. We\'ll build this one reward pair at a time as we scan through `zip(r1,r2)`. We\'ll also attach the reward value to each item so we can tally up the points later.\n\nWe can limit heap size to $$k$$ and eject the smallest element if we need to make space for an incoming item. Every time we eject an item, that means mouse 2 will be getting that cheese, so we increment the tally by $$r_2[i]$$. \n\nAt the end, the heap contains precisely the $$k$$ cheeses where mouse 1 has the greatest advantage. We add mouse 1\'s rewards for those cheese to the final tally and we\'re done.\n\n```python\nfrom heapq import heappush as push, heappop as pop\nclass Solution:\n    def miceAndCheese(self, r1: List[int], r2: List[int], k: int) -> int:\n        heap, ans = [], 0\n        for x,y in zip(r1, r2):\n            push(heap, (x-y,y))\n            if len(heap) > k:\n                ans += pop(heap)[1]\n        return ans + sum(d+y for d,y in heap)\n```\n##### Complexity of Heap Solution\nThe heap never gets larger than size $$k$$. Thus,\n\n- Time complexity: $$O(N \\log k)$$ \n- Space complexity: $$O(k)$$\n\nSince $$k\\leq n$$ this is better than the sorting solution when accounting for $$k$$. \n\n##### This is a streaming solution\n\nThis means that this will still solve the problem even if we are told the reward pairs one-by-one without knowledge of how many more rewards remain. In other words, this will work even if the reward pairs are generated on the fly.
['Sorting', 'Heap (Priority Queue)', 'Data Stream', 'Python3']