Minimum Amount of Time to Fill Cups - Solution & Explanation
Problem Statement
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 cold, warm, and hot water cups you need to fill respectively. Return the minimum number of seconds needed to fill up all the cups.
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 4 is the minimum number of seconds needed.
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 hot 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 warm 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:
amount.length == 30 <= amount[i] <= 100
Approach Overview
Problem Overview: You are given an array amount where each element represents the number of cold, warm, and hot cups to fill. Each second you can either fill two different types of cups or one cup of any type. The task is to compute the minimum number of seconds required to finish filling all cups.
Approach 1: Greedy Counting (O(1) time, O(1) space)
The key observation is that one second can process two different cup types simultaneously. The total work is the sum of all cups, but you cannot process more than one cup of the same type per second. Sort the three values or compute the maximum directly. The minimum time is max(max(amount), ceil(sum(amount)/2)). The first term handles the case where one type dominates, while the second term represents pairing cups whenever possible. This greedy reasoning avoids simulation and works in constant time because the array size is fixed. The approach relies on simple array manipulation and a classic greedy observation.
Approach 2: Priority Queue (Heap) Simulation (O(n log 3) time, O(1) space)
This method simulates the process using a max heap. Push the three cup counts into a priority queue. Each second, pop the two largest values, decrement both, and push them back if they are still positive. If only one type remains, decrement it alone. The heap ensures the two largest counts are always chosen, which maximizes parallel filling each second. Because the heap size never exceeds three elements, operations are cheap, but the loop runs for roughly the total number of seconds required.
Recommended for interviews: Interviewers usually expect the greedy observation. The heap simulation demonstrates understanding of priority queues, but the constant-time greedy formula shows stronger problem insight and leads to the most optimal solution.
Approach 1: Greedy Approach
The greedy approach involves selecting the largest possible numbers from the amount array to fill in pairs such that the number of seconds is minimized. By always aiming to fill two types of water at once, we can quickly reduce the total amount.
In this solution, we compute the sum and find the maximum of the given amounts. The minimum time to fill the cups is either half of the total amount rounded up or the maximum number in the array, whichever is greater. This is because the largest number cannot be exceeded by pairs of other numbers.
Complexity
Time Complexity: O(1), since we only perform a few operations on a fixed-size array.
Space Complexity: O(1), as only a few extra variables are used.
Approach 2: Priority Queue (Heap) Approach
This method uses a priority queue to always prioritize filling the largest cups first. By maintaining the heap order, we can dynamically get and reduce the largest values effectively.
Implementing a priority queue in C requires custom structures and functions to maintain the heap property, which can be tedious for a succinct example.
Complexity
Implementation-dependent; typically O(log n) for heap operations in custom implementations.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O(1), since we only perform a few operations on a fixed-size array. |
| Priority Queue (Heap) Approach | Implementation-dependent; typically O(log n) for heap operations in custom implementations. |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Formula | O(1) | O(1) | Best solution when recognizing the pairing insight between cup types |
| Priority Queue (Heap) Simulation | O(n log 3) ≈ O(n) | O(1) | Useful for understanding the process step-by-step or when extending to more cup types |
Video Solution
Weekly Contest 301 | Leetcode 2335 Minimum Amount of Time to Fill Cups | Easy Heaps • Coding Decoded • 2,546 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Minimum Amount of Time to Fill Cups easy or hard?
Minimum Amount of Time to Fill Cups Python/Java solution
How to solve Minimum Amount of Time to Fill Cups in O(n)?
What is the best approach for Minimum Amount of Time to Fill Cups?
Is Minimum Amount of Time to Fill Cups asked at Google/Amazon/Meta?
What data structure is used in Minimum Amount of Time to Fill Cups?
What is the time complexity of Minimum Amount of Time to Fill Cups?
Ready to solve this problem?
Practice Minimum Amount of Time to Fill Cups with our built-in code editor and test cases.
Practice on FleetCode