Minimum Amount of Time to Fill Cups — Easy Problem & Solution

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 == 3
• 0 <= amount[i] <= 100

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

1. Sort the three counts descending.
2. 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)

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Special Array I Easy
• Type of Triangle Easy
• Find the Losers of the Circular Game Easy
• Form Smallest Number From Two Digit Arrays Easy
• Delete Greatest Value in Each Row Easy
• The Employee That Worked on the Longest Task Easy