Difficulty: Easy | Acceptance: 60.20% | Paid: No Topics: Array, Greedy, Sorting, Heap (Priority Queue)
You have a water dispenser that can dispense cold, warm, and hot water. Every second, you can either fill up 2 cups with different types of water, or 1 cup of any type of water.
You are given a 0-indexed integer array amount of length 3 where amount[0], amount[1], and amount[2] denote the number of cups of cold, warm, and hot water needed to be filled respectively. Return the minimum number of seconds needed to fill up all the cups.
- Examples
- Constraints
- Mathematical Approach
- Sorting Simulation
- Max-Heap Approach
Examples
Example 1:
Input: amount = [1,4,2]
Output: 4
Explanation: One way to fill up the cups is:
Second 1: Fill up a cold cup and a warm cup.
Second 2: Fill up a warm cup and a hot cup.
Second 3: Fill up a warm cup and a hot cup.
Second 4: Fill up a warm cup.
It can be proven that you cannot fill up the cups in 3 seconds.
Example 2:
Input: amount = [5,4,4]
Output: 7
Explanation: One way to fill up the cups is:
Second 1: Fill up a cold cup and a warm cup.
Second 2: Fill up a cold cup and a warm cup.
Second 3: Fill up a cold cup and a warm cup.
Second 4: Fill up a warm cup and a hot cup.
Second 5: Fill up a cold cup and a hot cup.
Second 6: Fill up a cold cup and a hot cup.
Second 7: Fill up a hot cup.
Example 3:
Input: amount = [5,0,0]
Output: 5
Explanation: Every second, we fill up a cold cup.
Constraints
0 <= amount[i] <= 100
Mathematical Approach
Intuition The answer is the maximum of the largest cup count and half the total cups (rounded up). If one type dominates, we are limited by that count. Otherwise, we can pair cups optimally.
Steps
- Find the maximum value in the array
- Calculate the sum of all values
- Return max(max_value, (sum + 1) // 2)
class Solution:
def fillCups(self, amount: List[int]) -> int:
return max(max(amount), (sum(amount) + 1) // 2)
Complexity
- Time: O(1) - fixed size array
- Space: O(1)
- Notes: Most optimal solution with constant time and space
Sorting Simulation
Intuition Always fill the two types with the most remaining cups. This greedy strategy ensures we minimize total time.
Steps
- Sort the array in descending order
- While cups remain, decrement the two largest values
- Re-sort and repeat until all cups are filled
- Count the number of operations
class Solution:
def fillCups(self, amount: List[int]) -> int:
seconds = 0
while sum(amount) > 0:
amount.sort(reverse=True)
if amount[0] > 0 and amount[1] > 0:
amount[0] -= 1
amount[1] -= 1
elif amount[0] > 0:
amount[0] -= 1
seconds += 1
return seconds
Complexity
- Time: O(n log n) where n is the maximum cup count
- Space: O(1)
- Notes: Sorting at each iteration makes this less efficient than the mathematical approach
Max-Heap Approach
Intuition Use a max-heap to efficiently retrieve and update the two largest cup counts at each step.
Steps
- Push all cup counts into a max-heap
- While heap has more than one element, pop two largest values
- Decrement both and push back if still positive
- Count operations and add remaining single cup count
import heapq
class Solution:
def fillCups(self, amount: List[int]) -> int:
heap = [-a for a in amount if a > 0]
heapq.heapify(heap)
seconds = 0
while len(heap) > 1:
a = -heapq.heappop(heap)
b = -heapq.heappop(heap)
a -= 1
b -= 1
if a > 0:
heapq.heappush(heap, -a)
if b > 0:
heapq.heappush(heap, -b)
seconds += 1
if heap:
seconds += -heap[0]
return seconds
Complexity
- Time: O(n log n) where n is the maximum cup count
- Space: O(1) - heap has at most 3 elements
- Notes: More efficient than sorting simulation but still not as optimal as mathematical approach