Problem Description

You have a water dispenser with three types of water: cold, warm, and hot. The dispenser has two operating modes per second:

• Fill 2 cups with different types of water (e.g., 1 cold and 1 warm, or 1 warm and 1 hot, or 1 cold and 1 hot)
• Fill 1 cup of any single type of water

Given an integer array amount of length 3, where:

• amount[0] = number of cold water cups needed
• amount[1] = number of warm water cups needed
• amount[2] = number of hot water cups needed

Your task is to find the minimum number of seconds required to fill all the cups.

For example, if amount = [1, 4, 2], you need 1 cold cup, 4 warm cups, and 2 hot cups. One optimal strategy would be:

• Second 1: Fill 1 warm and 1 hot cup (remaining: [1, 3, 1])
• Second 2: Fill 1 warm and 1 hot cup (remaining: [1, 2, 0])
• Second 3: Fill 1 cold and 1 warm cup (remaining: [0, 1, 0])
• Second 4: Fill 1 warm cup (remaining: [0, 0, 0])

Total time: 4 seconds.

The solution uses a greedy approach: repeatedly fill cups from the two types with the most remaining cups until all cups are filled. This maximizes the use of the 2-cup filling mode and minimizes total time.

Intuition

The key insight is that we want to maximize the use of the 2-cup filling mode since it's twice as efficient as filling 1 cup at a time. To do this optimally, we should always try to fill from the two types with the most remaining cups.

Think about it this way: if we have [1, 4, 2] cups to fill, and we choose to fill the types with fewer cups first (say cold and hot), we'd end up with [0, 4, 1]. Now we're forced to fill warm cups one at a time for several seconds since we can't use the 2-cup mode when one type reaches 0.

Instead, if we always target the two types with the most cups, we keep the distribution more balanced. This ensures we can use the 2-cup mode for as long as possible.

The greedy strategy emerges naturally: at each second, sort the amounts and fill one cup from the type with the most cups (index 2 after sorting) and one cup from the type with the second-most cups (index 1 after sorting). If the second-highest is already 0, we can only fill 1 cup.

This approach works because:

1. The minimum time is bounded by max(amount) (worst case: filling one type entirely alone)
2. The minimum time is also bounded by (sum(amount) + 1) // 2 (best case: always filling 2 cups)
3. By always reducing the two largest values, we're working towards the best case scenario while avoiding getting stuck with a single large value

The solution continues this process until all cups are filled (when sum(amount) = 0).

Learn more about Greedy, Sorting and Heap (Priority Queue) patterns.

Solution Approach

The implementation uses a simple greedy simulation approach with sorting:

1. Initialize a counter: Start with ans = 0 to track the number of seconds elapsed.

2. Main loop: Continue while there are still cups to fill (while sum(amount) > 0):

3. Sort the amounts: At each iteration, sort the amount array so that:

   • amount[0] has the minimum value
   • amount[1] has the middle value
   • amount[2] has the maximum value

4. Fill cups greedily:

   • Increment the time counter: ans += 1
   • Always fill one cup from the type with the most cups: amount[2] -= 1
   • Try to fill a second cup from the type with the second-most cups: amount[1] = max(0, amount[1] - 1)
   • The max(0, amount[1] - 1) ensures we don't go negative if amount[1] is already 0

5. Return the result: Once all cups are filled (sum becomes 0), return ans.

The time complexity is O(n * m) where n is the total number of cups and m is the number of water types (3 in this case). Since we sort 3 elements in each iteration, sorting takes O(1) time. The space complexity is O(1) as we only modify the input array in-place.

This greedy approach guarantees the minimum time because it maximizes the use of the 2-cup filling mode by always targeting the two most abundant types, preventing any single type from becoming disproportionately large compared to others.

Example Walkthrough

Let's walk through a small example with amount = [1, 4, 2] to illustrate the solution approach.

Initial state: We need 1 cold cup, 4 warm cups, and 2 hot cups.

Second 1:

• Current amounts: [1, 4, 2]
• Sort the array: [1, 2, 4] (ascending order)
• Fill 1 cup from the largest (index 2): 4 - 1 = 3
• Fill 1 cup from the second-largest (index 1): 2 - 1 = 1
• After second 1: [1, 1, 3] → rearranged back to original positions: [1, 3, 1]

Second 2:

• Current amounts: [1, 3, 1]
• Sort the array: [1, 1, 3]
• Fill 1 cup from the largest (index 2): 3 - 1 = 2
• Fill 1 cup from the second-largest (index 1): 1 - 1 = 0
• After second 2: [1, 0, 2] → rearranged back: [1, 2, 0]

Second 3:

• Current amounts: [1, 2, 0]
• Sort the array: [0, 1, 2]
• Fill 1 cup from the largest (index 2): 2 - 1 = 1
• Fill 1 cup from the second-largest (index 1): 1 - 1 = 0
• After second 3: [0, 0, 1] → rearranged back: [0, 1, 0]

Second 4:

• Current amounts: [0, 1, 0]
• Sort the array: [0, 0, 1]
• Fill 1 cup from the largest (index 2): 1 - 1 = 0
• Try to fill from second-largest (index 1): max(0, 0 - 1) = 0 (already 0, so only 1 cup filled)
• After second 4: [0, 0, 0]

Result: All cups filled in 4 seconds.

The key observation is that by always targeting the two types with the most cups remaining, we maintained balance and used the efficient 2-cup mode for 3 out of 4 seconds. Only in the final second did we need to use the single-cup mode when only one type had cups remaining.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n²) where n = max(amount)

The while loop runs until all cups are filled (when sum(amount) = 0). In each iteration:

• sum(amount) takes O(1) time (array has fixed size of 3)
• sort() takes O(1) time (sorting 3 elements is constant)
• The other operations are O(1)

The key insight is determining how many iterations occur. In the worst case, we decrease the sum by at least 1 per iteration (when only one type has cups remaining). The maximum number of iterations is max(amount) initially, which we can denote as n. Therefore, the overall time complexity is O(n) iterations × O(1) per iteration = O(n).

However, upon closer inspection, the initial sum could be up to 3n where n = max(amount), and in the worst case we might need up to sum(amount) iterations. Since we're sorting in each iteration and the sum decreases by 1 or 2 each time, the time complexity is O(sum(amount)) which is O(n) where n represents the total number of cups to fill.

Space Complexity: O(1)

The algorithm modifies the input array in-place and only uses a constant amount of extra space for the variable ans. No additional data structures are created that scale with the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Inefficient Time Complexity with Sorting

The current solution sorts the array in every iteration, which can be inefficient when dealing with large numbers. While sorting 3 elements is O(1), the total number of iterations can be as high as sum(amount), making the overall complexity O(n) where n is the total cups.

Better Approach: Use a max heap or calculate the result mathematically without simulation.

2. Missing the Mathematical Insight

The simulation approach works but misses an elegant mathematical solution. The minimum time needed is actually max(max(amount), ceil(sum(amount) / 2)).

Explanation:

• We need at least ceil(sum(amount) / 2) seconds because we can fill at most 2 cups per second
• We need at least max(amount) seconds because the type with the most cups sets a lower bound
• The answer is the maximum of these two values

Optimized Solution:

class Solution:
    def fillCups(self, amount: List[int]) -> int:
        # Mathematical approach - O(1) time
        total = sum(amount)
        max_cups = max(amount)
      
        # Answer is max of:
        # 1. The type with most cups (lower bound)
        # 2. Half the total (rounded up) since we fill 2 cups per second
        return max(max_cups, (total + 1) // 2)

3. Unnecessary Memory Operations

The current solution modifies the array in place with sorting at each step, which involves unnecessary memory operations.

Alternative Using Heap:

import heapq

class Solution:
    def fillCups(self, amount: List[int]) -> int:
        # Use max heap for efficient access to largest elements
        # Python has min heap, so negate values
        heap = [-x for x in amount if x > 0]
        heapq.heapify(heap)
      
        seconds = 0
        while heap:
            seconds += 1
          
            # Pop the largest
            first = -heapq.heappop(heap)
          
            if heap:
                # Pop the second largest
                second = -heapq.heappop(heap)
              
                # Put back if still has cups
                if first - 1 > 0:
                    heapq.heappush(heap, -(first - 1))
                if second - 1 > 0:
                    heapq.heappush(heap, -(second - 1))
            # If no second type available, we just filled one cup
          
        return seconds

4. Not Recognizing Edge Cases

The solution handles the case where all values become 0, but developers might forget to handle:

• When input contains zeros initially: [0, 5, 0]
• When only one type has cups: [0, 0, 7]

The mathematical solution naturally handles these cases without special logic.