LeetCode 2335 - Minimum Amount of Time to Fill Cups

LeetCode Problem 2335

Difficulty: 🟢 Easy
Topics: Array, Greedy, Sorting, Heap (Priority Queue)

Solution

Problem Understanding

The problem gives us an array amount of length 3. Each index represents the number of cups that need to be filled for a specific water type:

• amount[0] represents cold water cups
• amount[1] represents warm water cups
• amount[2] represents hot water cups

Every second, the machine can perform exactly one of these operations:

1. Fill one cup of any type
2. Fill two cups simultaneously, but only if they are different types

The goal is to determine the minimum number of seconds required to fill all cups.

The important detail is that the machine becomes more efficient when two different water types are still available. If at least two categories still contain cups, we should try to fill two cups in one second whenever possible.

The constraints are very small:

• The array length is always 3
• Each value is between 0 and 100

Because the input size is tiny, almost any reasonable algorithm will run quickly. However, the problem is mainly about recognizing the mathematical observation that determines the optimal answer.

Several edge cases are important:

• One category may dominate all others, such as [10,1,1]
• Some categories may already be empty, such as [5,0,0]
• All categories may be balanced, such as [4,4,4]
• All values may be zero, such as [0,0,0]

A naive implementation can make mistakes when one category is much larger than the others. Even if we pair cups efficiently, eventually the largest category may still require individual filling operations.

Approaches

Brute Force Approach

A straightforward simulation approach repeatedly performs the best possible operation each second.

At every step:

1. Sort the three amounts
2. If the two largest values are positive, decrement both
3. Otherwise decrement the single remaining positive value
4. Count how many seconds were used

This greedy simulation works because every second we try to maximize efficiency by filling two cups whenever possible.

Although this approach is completely valid, it repeatedly sorts or scans the array during every operation. Since the values are small, this still runs quickly enough, but it is not the most elegant solution.

Key Insight for the Optimal Solution

The optimal solution comes from observing two lower bounds on the answer.

First, every second can fill at most two cups. Therefore:

$$\text{minimum time} \geq \left\lceil \frac{\text{total cups}}{2} \right\rceil$$

If the total number of cups is sum, then even in the best case we need at least half that many seconds.

Second, the largest category creates another lower bound. Suppose one type contains more cups than the other two combined. Eventually, the smaller categories will run out, and the remaining cups of the largest category must be filled one at a time.

Therefore:

$$\text{minimum time} \geq \max(amount)$$

The remarkable observation is that the answer is simply the larger of these two bounds:

$$\text{answer} = \max\left(\max(amount), \left\lceil \frac{\sum amount}{2} \right\rceil\right)$$

This works because:

• If the cups are balanced enough, pairing operations dominate, so the answer is based on total cups
• If one category dominates, the answer is based on the largest pile

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(S)	O(1)	Simulates every second, where S is total cups
Optimal	O(1)	O(1)	Uses a mathematical observation

Algorithm Walkthrough

Optimal Algorithm

1. Compute the total number of cups by summing all three values.

This tells us how much total work must be completed. 2. Compute the maximum value among the three categories.

This identifies whether one water type dominates the others. 3. Compute the minimum possible time based on total cups.

Since one second can fill at most two cups, we need at least:

$$\left\lceil \frac{\text{total}}{2} \right\rceil$$

In integer arithmetic, this can be written as:

$$\frac{total + 1}{2}$$ 4. Return the larger value between:

• the largest category
• half the total cups rounded up

This guarantees both constraints are satisfied.

Why it works

There are two unavoidable limits.

The first limit comes from throughput. Since at most two cups can be filled per second, the total work requires at least half the number of cups in seconds.

The second limit comes from imbalance. If one category contains many more cups than the others, eventually the other categories disappear, forcing the remaining cups to be processed one by one.

The optimal strategy always achieves whichever lower bound is larger, which proves the formula is correct.

Python Solution

from typing import List

class Solution:
    def fillCups(self, amount: List[int]) -> int:
        total_cups = sum(amount)
        largest_group = max(amount)

        minimum_by_pairing = (total_cups + 1) // 2

        return max(largest_group, minimum_by_pairing)

The implementation directly follows the mathematical derivation.

First, we compute the total number of cups using sum(amount). This gives the total workload.

Next, we compute the largest category using max(amount). This captures the imbalance constraint.

The expression (total_cups + 1) // 2 performs ceiling division for integers. For example:

• 5 becomes 3
• 6 becomes 3

Finally, we return the larger of the two lower bounds.

The implementation is extremely compact because the main challenge is recognizing the mathematical property behind the problem.

Go Solution

func fillCups(amount []int) int {
	totalCups := amount[0] + amount[1] + amount[2]

	largestGroup := amount[0]
	if amount[1] > largestGroup {
		largestGroup = amount[1]
	}
	if amount[2] > largestGroup {
		largestGroup = amount[2]
	}

	minimumByPairing := (totalCups + 1) / 2

	if largestGroup > minimumByPairing {
		return largestGroup
	}

	return minimumByPairing
}

The Go implementation follows the same logic as the Python version.

Go does not provide built in max or sum functions for slices, so we compute them manually.

Integer division in Go automatically truncates toward zero, so (totalCups + 1) / 2 correctly performs ceiling division for positive integers.

There are no overflow concerns because all values are at most 100, making the total at most 300.

Worked Examples

Example 1

Input:

amount = [1,4,2]

First compute the totals.

Variable	Value
Total Cups	7
Largest Group	4
Ceiling(7 / 2)	4

Now compute:

$$\max(4, 4) = 4$$

Answer:

4

A valid schedule is:

Second	Action
1	Fill cold + warm
2	Fill warm + hot
3	Fill warm + hot
4	Fill warm

Example 2

Input:

amount = [5,4,4]

Compute values:

Variable	Value
Total Cups	13
Largest Group	5
Ceiling(13 / 2)	7

Now compute:

$$\max(5, 7) = 7$$

Answer:

7

The total number of cups dominates here because the categories are fairly balanced.

Example 3

Input:

amount = [5,0,0]

Compute values:

Variable	Value
Total Cups	5
Largest Group	5
Ceiling(5 / 2)	3

Now compute:

$$\max(5, 3) = 5$$

Answer:

5

Even though two cups can theoretically be filled each second, there are no different types available for pairing. Every cup must be filled individually.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	Only a few arithmetic operations are performed
Space	O(1)	No extra data structures are used

The algorithm processes exactly three numbers regardless of input values. Since the array size never changes, both time and space usage remain constant.

Test Cases

from typing import List

class Solution:
    def fillCups(self, amount: List[int]) -> int:
        total_cups = sum(amount)
        largest_group = max(amount)
        return max(largest_group, (total_cups + 1) // 2)

solution = Solution()

assert solution.fillCups([1, 4, 2]) == 4  # Example 1
assert solution.fillCups([5, 4, 4]) == 7  # Example 2
assert solution.fillCups([5, 0, 0]) == 5  # Example 3

assert solution.fillCups([0, 0, 0]) == 0  # No cups at all
assert solution.fillCups([1, 1, 1]) == 2  # Balanced small case
assert solution.fillCups([2, 2, 2]) == 3  # Perfect pairing every second
assert solution.fillCups([10, 1, 1]) == 10  # Dominant category
assert solution.fillCups([3, 3, 7]) == 7  # Largest pile dominates
assert solution.fillCups([4, 4, 5]) == 7  # Total cups dominates
assert solution.fillCups([100, 100, 100]) == 150  # Maximum balanced values
assert solution.fillCups([100, 0, 0]) == 100  # Maximum single category
assert solution.fillCups([8, 5, 3]) == 8  # Equal to largest category

Test Case Summary

Test	Why
[1,4,2]	Validates standard mixed case
[5,4,4]	Validates balanced large groups
[5,0,0]	Validates single nonzero category
[0,0,0]	Validates empty input
[1,1,1]	Validates odd total with balanced groups
[2,2,2]	Validates perfect pairing
[10,1,1]	Validates heavily dominant category
[3,3,7]	Validates largest group lower bound
[4,4,5]	Validates total cups lower bound
[100,100,100]	Validates maximum balanced constraints
[100,0,0]	Validates maximum unbalanced constraints
[8,5,3]	Validates boundary between the two rules

Edge Cases

Only One Nonzero Category

An input like [5,0,0] is important because pairing operations are impossible. A buggy implementation might incorrectly assume two cups can always be processed together.

The formula handles this naturally because the largest category becomes the dominant lower bound. The answer correctly becomes 5.

Perfectly Balanced Categories

An input like [4,4,4] represents the ideal pairing scenario. Every second can process two cups until completion.

The total number of cups is 12, so the answer becomes:

$$12 / 2 = 6$$

The implementation correctly identifies that the throughput bound dominates.

One Category Larger Than the Sum of Others

An input like [10,1,1] is a common source of logical mistakes.

Initially, some cups can be paired:

• 10 with 1
• 9 with 1

After that, only one category remains, forcing individual processing for the remaining cups.

The formula correctly returns 10, because the largest category exceeds half the total workload.

All Values Are Zero

An input like [0,0,0] checks whether the implementation handles empty work correctly.

The total cups and largest category are both zero, so the answer is zero. The implementation returns this naturally without requiring any special handling.