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] <= 100The 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.
C++
Java
Python
C#
JavaScript
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.
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.
C++
Java
Python
C#
JavaScript
Implementation-dependent; typically O(log n) for heap operations in custom implementations.
| 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. |
Minimum Cost for Tickets - Dynamic Programming - Leetcode 983 - Python • NeetCode • 75,555 views views
Watch 9 more video solutions →Practice Minimum Amount of Time to Fill Cups with our built-in code editor and test cases.
Practice on FleetCode