#2335

Easy

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Minimum Amount of Time to Fill Cups

Determine the minimum seconds to fill cups of cold, warm, and hot water using a greedy selection strategy and invariant check.

array greedy sorting heap priority queue

Problem Statement

You are given three types of water cups: cold, warm, and hot. Each second, you can fill either one cup of any type or two cups of different types simultaneously. Determine the minimum number of seconds required to fill all cups given an array amount = [cold, warm, hot].

Implement a function that takes a 0-indexed array amount of length 3 where amount[0], amount[1], and amount[2] represent the number of cups for cold, warm, and hot water respectively. Return the fewest seconds needed to fill all cups under the dispensing rules.

Examples

Example 1

Input: amount = [1,4,2]

Output: 4

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

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

Every second, we fill up a cold cup.

Constraints

amount.length == 3
0 <= amount[i] <= 100

Solution Approach

Greedy Max Pair Selection

Each second, identify the two cup types with the largest remaining counts and fill one cup of each. This ensures that every second contributes maximally to reducing total cups, minimizing overall time.

Invariant Validation

Check that the largest remaining cup count never exceeds half the sum of all remaining cups. This invariant guarantees that the greedy max-pair choice leads to a valid minimal time solution.

Simple Implementation Using Sorting or Heap

Sort the cup counts each iteration or use a max heap to efficiently select the two largest values. Decrement counts after each step until all cups are filled, accumulating the total seconds.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(1) with fixed-length arrays since operations involve only three elements, or O(n log n) if generalized with a heap. Space complexity is O(1) for in-place operations or O(n) if a heap is used.

What Interviewers Usually Probe

Consider the effect of filling two different types each second versus one type.
Think about whether the largest cup count ever dictates the minimum total time.
Watch for off-by-one errors when decrementing cup counts each second.

Common Pitfalls or Variants

Common pitfalls

Attempting to fill cups in arbitrary order without maximizing each second wastes time.
Failing to check that the largest cup type does not exceed half of remaining cups may yield incorrect results.
Neglecting to handle cases where only one type remains can miscount total seconds.

Follow-up variants

Generalize to more than three cup types, requiring priority queues to select the largest pair each second.
Allow filling up to k cups per second if types are distinct, adjusting the greedy selection accordingly.
Introduce unequal fill rates for each type, requiring weighted greedy selection to minimize total time.

FAQ

What is the fastest approach to solve Minimum Amount of Time to Fill Cups?

Use a greedy strategy selecting the two largest remaining cup counts each second and validate that the largest does not exceed half the total remaining.

Can we fill two cups of the same type in one second?

No, the rules allow filling either one cup of any type or two cups of different types per second.

Does the array length always matter?

Yes, the problem specifically uses an array of length 3 representing cold, warm, and hot cups, simplifying selection.

What data structures help implement this efficiently?

Sorting the array each iteration or using a max heap lets you efficiently pick the two largest counts per second.

How does the greedy choice plus invariant pattern apply here?

It ensures each second reduces the largest counts optimally while checking that no single type dominates, guaranteeing minimal total time.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

class Solution:
    def fillCups(self, amount: List[int]) -> int:
        ans = 0
        while sum(amount):
            amount.sort()
            ans += 1
            amount[2] -= 1
            amount[1] = max(0, amount[1] - 1)
        return ans

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

class Solution:
    def fillCups(self, amount: List[int]) -> int:
        ans = 0
        while sum(amount):
            amount.sort()
            ans += 1
            amount[2] -= 1
            amount[1] = max(0, amount[1] - 1)
        return ans

Continue Practicing

#2333 minimum sum of squared difference #2357 make array zero by subtracting equal amounts #2406 divide intervals into minimum number of groups