# Minimum Amount of Time to Fill Cups
**Difficulty:** EASY
[External](https://leetcode.com/problems/minimum-amount-of-time-to-fill-cups)
Canonical: https://scaleengineer.com/dsa/problems/minimum-amount-of-time-to-fill-cups
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Heap (Priority Queue)
---
## Problem
You have a water dispenser that can dispense cold, warm, and hot water. Every second, you can either fill up `2` cups with **different** types of water, or `1` cup of any type of water.

You are given a **0-indexed** integer array `amount` of length `3` where `amount[0]`, `amount[1]`, and `amount[2]` denote the number of cold, warm, and hot water cups you need to fill respectively. Return _the **minimum** number of seconds needed to fill up all the cups_.

**Example 1:**

**Input:** amount = [1,4,2]
**Output:** 4
**Explanation:** 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
**Explanation:** 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
**Explanation:** Every second, we fill up a cold cup.

**Constraints:**

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

# Approaches
## Simulation with Sorting
This approach simulates the process of filling cups second by second. At each second, we greedily choose to fill cups from the two types that have the most cups remaining. This is a sound greedy strategy because we want to maximize the use of the more efficient 2-cup operation. Pairing the largest piles helps keep the pile sizes balanced, preventing a situation where one pile is left with a large number of cups that must be filled one by one at the end.
**Time:** O(S), where S is the total number of cups. The loop runs at most S/2 times. Inside the loop, sorting an array of size 3 is a constant time operation, O(1). Thus, the total time is proportional to the sum of the amounts. Given the constraints, this is very efficient. · **Space:** O(1), as we modify the input array in-place or use a constant amount of extra space.
**Pros:** Simple to understand and implement.; Directly models the greedy strategy without complex data structures.
**Cons:** Less efficient than other approaches due to the simulation loop.; The repeated sorting in each iteration, while `O(1)` for a fixed size of 3, is computationally more work than necessary.
### Explanation
The algorithm works by repeatedly finding the two largest amounts, decrementing them, and counting one second. We use the `amount` array itself to keep track of the counts. In a loop, we sort the array at each step. This places the two largest amounts at indices 1 and 2, making them easy to access and modify. We decrement these two largest amounts and increment our time counter. The loop continues as long as there are at least two types of cups with a positive count. Once the loop finishes, it's possible that one type of cup remains. The time to fill these is simply their count, which we add to our total time before returning the result.

```java
import java.util.Arrays;

class Solution {
    public int fillCups(int[] amount) {
        int seconds = 0;
        Arrays.sort(amount);
        // Loop as long as the two largest piles are non-empty
        while (amount[1] > 0) {
            seconds++;
            // Take one from each of the two largest piles
            amount[1]--;
            amount[2]--;
            // Re-sort to find the new two largest piles
            Arrays.sort(amount);
        }
        // At this point, amount[0] and amount[1] are 0.
        // Any remaining cups are in amount[2] and must be filled one by one.
        seconds += amount[2];
        return seconds;
    }
}
```
### Algorithm
*   Initialize a variable `seconds` to 0.
*   Create a loop that continues as long as at least two types of cups have a non-zero count. A simple way to check this is to sort the array and check if the second-largest element (`amount[1]`) is greater than 0.
*   Inside the loop:
    1.  Increment `seconds`.
    2.  Sort the `amount` array to easily find the two largest counts.
    3.  Decrement the two largest counts (`amount[2]` and `amount[1]`).
*   After the loop terminates, at most one type of cup will have a non-zero count (which will be `amount[2]` after the final sort). The time to fill these remaining cups is equal to their count.
*   Add the remaining count (`amount[2]`) to `seconds`.
*   Return `seconds`.

## Greedy Simulation with Priority Queue
This approach is a more optimized implementation of the same greedy strategy used in the sorting approach. Instead of sorting the array in each iteration to find the two largest amounts, we use a max-priority queue. A priority queue is a data structure specifically designed to provide efficient access to the maximum (or minimum) element, making it a natural fit for this problem.
**Time:** O(S), where S is the total number of cups. Each operation on the priority queue (add/poll) takes O(log k) time, where k is the number of elements. Since k is fixed at 3, this is O(1). The loop runs proportional to S times, giving a total time complexity of O(S). · **Space:** O(1), as the priority queue will store at most 3 elements.
**Pros:** An efficient and standard way to implement a greedy algorithm that repeatedly needs the largest elements.; Asymptotically faster than sorting for a larger number of cup types.
**Cons:** Slightly more complex to implement than the sorting approach due to the use of a Priority Queue.; Still less efficient than the direct mathematical formula.
### Explanation
We insert the initial non-zero cup counts into a max-priority queue. This data structure will always keep the largest counts at the top, ready to be extracted. We then loop as long as the priority queue contains two or more elements. In each iteration, which represents one second, we extract the two largest counts, decrement them, and if they are still greater than zero, we insert them back. This elegantly simulates the process of pairing the two most abundant types of cups. When the loop terminates, the queue will have at most one element. If it's not empty, this represents the remaining cups of a single type that must be filled one by one. The time for this is their count, which we add to our total time.

```java
import java.util.Collections;
import java.util.PriorityQueue;

class Solution {
    public int fillCups(int[] amount) {
        // Create a max-heap to always get the largest counts easily
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for (int count : amount) {
            if (count > 0) {
                pq.add(count);
            }
        }

        int seconds = 0;
        while (pq.size() > 1) {
            seconds++;
            int firstMax = pq.poll();
            int secondMax = pq.poll();

            firstMax--;
            secondMax--;

            if (firstMax > 0) {
                pq.add(firstMax);
            }
            if (secondMax > 0) {
                pq.add(secondMax);
            }
        }

        if (!pq.isEmpty()) {
            seconds += pq.poll();
        }

        return seconds;
    }
}
```
### Algorithm
*   Create a max-priority queue (in Java, `PriorityQueue` with a reverse order comparator).
*   Add all non-zero counts from the `amount` array into the priority queue.
*   Initialize `seconds = 0`.
*   While the priority queue contains more than one element:
    1.  Increment `seconds`.
    2.  Extract the two largest elements (`max1` and `max2`) using `poll()`.
    3.  Decrement both `max1` and `max2`.
    4.  If the decremented values are still greater than 0, add them back to the priority queue.
*   After the loop, if the queue is not empty, it contains the count of the last remaining type of cup. Add this value to `seconds`.
*   Return `seconds`.

## Optimal Mathematical Approach
By analyzing the problem constraints and the greedy strategy, we can derive a direct mathematical formula to solve the problem in constant time. This is the most optimal approach. The key insight is that the minimum time is limited by two things: the total number of cups to fill and the amount of the most frequent type of cup.
**Time:** O(1), as we only perform a single pass over an array of fixed size 3. · **Space:** O(1), as we only use a few variables to store the max and sum.
**Pros:** Extremely efficient with constant time and space complexity.; Elegant and concise solution.
**Cons:** The logic is less intuitive than a direct simulation and requires a mathematical insight to derive.
### Explanation
Let the counts of the three types of cups be stored in the `amount` array.

1.  **Bottleneck 1: The Largest Pile.** Let `maxVal` be the count of the most frequent cup type. Even if we pair this cup type with another type every single second, it will take at least `maxVal` seconds to empty this pile. Therefore, `time >= maxVal`.

2.  **Bottleneck 2: The Total Work.** Let `sum` be the total number of cups. Since we can fill at most 2 cups per second, the time required is at least `ceil(sum / 2)`. Therefore, `time >= ceil(sum / 2)`.

Combining these, the minimum time must be at least `max(maxVal, ceil(sum / 2))`. It can be proven that this lower bound is always achievable. If the largest pile is the bottleneck (`maxVal > sum - maxVal`), the time is `maxVal`. Otherwise, the piles are balanced enough that the total number of cups is the bottleneck, and the time is `ceil(sum / 2)`. The formula elegantly covers both cases.

```java
import java.util.Arrays;

class Solution {
    public int fillCups(int[] amount) {
        int maxVal = 0;
        int sum = 0;
        for (int count : amount) {
            maxVal = Math.max(maxVal, count);
            sum += count;
        }

        // The minimum time is the maximum of two quantities:
        // 1. The largest number of cups of a single type (maxVal).
        // 2. The total number of cups divided by 2, rounded up.
        // (sum + 1) / 2 is a common way to calculate ceil(sum / 2) using integer division.
        return Math.max(maxVal, (sum + 1) / 2);
    }
}
```
### Algorithm
*   Iterate through the `amount` array to find two values: the maximum count (`maxVal`) and the total sum of counts (`sum`).
*   The minimum time required is constrained by two factors:
    1.  The count of the most numerous cup type (`maxVal`). We need at least `maxVal` seconds to fill them all.
    2.  The total number of cups (`sum`). Since we can fill at most 2 cups per second, we need at least `ceil(sum / 2)` seconds.
*   The final answer is the maximum of these two lower bounds: `max(maxVal, ceil(sum / 2))`.
*   `ceil(sum / 2)` can be calculated using integer arithmetic as `(sum + 1) / 2`.
*   Return this calculated value.

# Solutions
### Java

```java
class Solution {
public
  int fillCups(int[] amount) {
    int ans = 0;
    while (amount[0] + amount[1] + amount[2] > 0) {
      Arrays.sort(amount);
      ++ans;
      amount[2]--;
      amount[1] = Math.max(0, amount[1] - 1);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int fillCups(vector<int> &amount) {
    int ans = 0;
    while (amount[0] + amount[1] + amount[2]) {
      sort(amount.begin(), amount.end());
      ++ans;
      amount[2]--;
      amount[1] = max(0, amount[1] - 1);
    }
    return ans;
  }
};

```

### Python

```python
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

```