O(1) Time & Space, Plus Two Other Approaches with Explanations! 🥃🧊🔥
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem involves determining the minimum amount of time needed to fill three types 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem involves determining the minimum amount of time needed to fill three types of cups, each requiring a different number of fills. The main insight is that in each unit of time, we can fill at most two different types of cups. Therefore, our strategy should aim to maximize the efficiency of each time unit by always trying to fill the two types of cups that have the most remaining fills required.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThere are several approaches to solve this problem:\n\n1. **Direct Comparison and Sorting for Length 3 Array**: For an array of fixed length 3, we can directly sort and compare the elements to determine the minimum time required. If the maximum number of fills required is greater than the sum of the other two, the answer is simply the maximum value. Otherwise, the answer is half the total fills rounded up.\n\n2. **Sorting for Arbitrary Length Array**: For arrays of arbitrary length, sorting the array and comparing the maximum value with half the total fills provides an efficient solution.\n\n3. **Max Heap**: Using a max heap, we can always pair the two most filled cup types in each unit of time. This approach ensures that we are efficiently reducing the highest fills first.\n\n# Complexity\n- Time complexity:\n  - `fillCups`: $$O(1)$$ because sorting and comparing a fixed-length array takes constant time.\n  - `fillCups2`: $$O(n \\log n)$$ due to sorting the array.\n  - `fillCups3`: $$O(n \\log n)$$ due to heap operations.\n\n- Space complexity:\n  - `fillCups`: $$O(1)$$ as it uses constant extra space.\n  - `fillCups2`: $$O(n)$$ due to sorting, which requires additional space for the sorted array.\n  - `fillCups3`: $$O(n)$$ due to the space needed for the max heap.\n\n# Code\n```python\nclass Solution:\n    def fillCups(self, amount: List[int]) -> int:\n        # Sorting for Length 3 Array\n        if amount[0] > amount[1]: amount[0], amount[1] = amount[1], amount[0]\n        if amount[1] > amount[2]: amount[1], amount[2] = amount[2], amount[1]\n        if amount[0] > amount[1]: amount[0], amount[1] = amount[1], amount[0]\n\n        if amount[2] >= amount[0] + amount[1]: # Max cup number give lower bound.\n            return amount[2]\n        \n        return ((amount[0] + amount[1] + amount[2]) + 1) // 2 # Filling times halves (2 cups per filling).\n\n        # O(1) time.\n        # O(1) auxiliary space.\n        # O(1) total space.\n        \n\n    def fillCups2(self, amount: List[int]) -> int:\n        # Sorting for Arbitrary Length Array\n        amount.sort()    \n        max_cups = amount[-1]\n        total_cups = sum(amount)\n        return max(max_cups, (total_cups + 1) // 2)\n\n        # O(n * log(n)) time.\n        # O(n) auxiliary space.\n        # O(n) total space.\n\n\n    def fillCups3(self, amount: List[int]) -> int:\n        # Max Heap\n        max_heap = [-num_cups for num_cups in amount if num_cups > 0]\n        heapq.heapify(max_heap)\n\n        seconds = 0\n        while max_heap:\n            if len(max_heap) >= 2:\n                cups_type_1, cups_type_2 = heapq.heappop(max_heap), heapq.heappop(max_heap) \n                cups_type_1, cups_type_2 = cups_type_1 + 1, cups_type_2 + 1\n\n                if cups_type_1 < 0:\n                    heapq.heappush(max_heap, cups_type_1)\n                if cups_type_2 < 0:\n                    heapq.heappush(max_heap, cups_type_2)\n                    \n            else:\n                cups_type_1 = heapq.heappop(max_heap)\n                cups_type_1 += 1\n\n                if cups_type_1 < 0:\n                    heapq.heappush(max_heap, cups_type_1)\n\n            seconds += 1\n\n        return seconds \n\n        # O(n * log(n)) time.\n        # O(n) auxiliary space.\n        # O(n) total space.\n```\nUPVOTE IF HELPFUL \uD83E\uDD19\nTHANKS
['Python3']