Minimum Amount of Time to Fill Cups — Problem & Solution
Minimum Amount of Time to Fill Cups solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Minimum Amount of Time to Fill Cups is an easy coding problem on arrays, math and greedy, asked in Amazon, Google and Infosys interviews.
- Difficulty: Easy
- Topics: Arrays, Math, Greedy, Heap
- Asked at: Amazon, Google, Infosys
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A water dispenser offers cold, warm and hot water. Each second you may fill either two cups of different types or one cup of any type.
Given amount = [cold, warm, hot], return the minimum number of seconds to fill all the cups.
Example 1
Input: amount = [1,4,2]
Output: 4
Explanation: Pair the 4 warm cups with the others, then finish alone.
Example 2
Input: amount = [5,4,4]
Output: 7
Explanation: The total is 13, and ceil(13 / 2) is 7.
Example 3
Input: amount = [5,0,0]
Output: 5
Explanation: One type only, so no pairing is possible.
Constraints
amount.length == 30 <= amount[i] <= 100
Hints for Minimum Amount of Time to Fill Cups
Hint 1
Two lower bounds apply: the largest single count, and half the total rounded up.
Hint 2
The answer is the larger of the two.
Hint 3
Pairing the two largest remaining counts each second achieves it.
How to solve Minimum Amount of Time to Fill Cups
Two obvious lower bounds turn out to be jointly sufficient. Each second fills at most two cups, so at least ceil(total / 2) seconds are needed; and the largest type needs at least its own count of seconds, since two cups of the same type cannot be filled together.
Approach
- Sort the three counts descending.
- Return
max(largest, ceil(total / 2)).
Why it works
If the largest count exceeds the other two combined, every second must include one cup of that type, so its count is the answer. Otherwise the counts can be paired down two at a time — always pairing the two largest remaining keeps them balanced enough that no type is ever left stranded — and ceil(total / 2) seconds suffice.
Complexity
- Time —
O(1) - Space —
O(1)
Pitfalls
- Taking only
ceil(total / 2)fails on inputs like[5,0,0]. - Taking only the maximum fails on
[5,4,4]. - Integer division must round up:
(total + 1) / 2.
Reference solution
Python
from typing import List
def fillCups(amount: List[int]) -> int:
a = sorted(amount, reverse=True)
total = sum(a)
return max(a[0], (total + 1) // 2)Java
public static int fillCups(int[] amount) {
int[] a = amount.clone();
Arrays.sort(a);
int total = a[0] + a[1] + a[2];
return Math.max(a[2], (total + 1) / 2);
}C++
int fillCups(vector<int>& amount) {
vector<int> a = amount;
sort(a.begin(), a.end());
int total = a[0] + a[1] + a[2];
return max(a[2], (total + 1) / 2);
}JavaScript
var fillCups = function(amount) {
var a = amount.slice().sort(function(x, y) { return y - x; });
var total = a[0] + a[1] + a[2];
return Math.max(a[0], Math.floor((total + 1) / 2));
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Greedy Algorithms