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 theminimum number of seconds needed to fill up all the cups.

Examples

Example 1

1
2
3
4
5
6
7
8

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

1
2
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

Solution

Method 1 – Greedy Maximum Selection

Intuition

At each second, we can fill either two cups of different types or one cup of any type. To minimize the time, always fill the two largest remaining cup types together. The answer is the maximum of the largest cup count and the ceiling of half the total cups.

Approach

  1. Sort the amount array.
  2. The minimum seconds needed is the maximum of:
    • The largest value in amount (since you can’t fill more than one of the same type per second).
    • The ceiling of half the sum of all cups (since you can fill at most two cups per second).
  3. Return the result.

Code

1
2
3
4
5
6
7

class Solution {
public:
    int fillCups(vector<int>& amount) {
        sort(amount.begin(), amount.end());
        return max(amount[2], (amount[0] + amount[1] + amount[2] + 1) / 2);
    }
};
1
2
3
4
5
6

func fillCups(amount []int) int {
    sort.Ints(amount)
    sum := amount[0] + amount[1] + amount[2]
    return max(amount[2], (sum+1)/2)
}
func max(a, b int) int { if a > b { return a } else { return b } }
1
2
3
4
5
6
7

class Solution {
    public int fillCups(int[] amount) {
        Arrays.sort(amount);
        int sum = amount[0] + amount[1] + amount[2];
        return Math.max(amount[2], (sum+1)/2);
    }
}
1
2
3
4
5
6
7

class Solution {
    fun fillCups(amount: IntArray): Int {
        amount.sort()
        val sum = amount.sum()
        return maxOf(amount[2], (sum+1)/2)
    }
}
1
2
3

def fill_cups(amount: list[int]) -> int:
    amount.sort()
    return max(amount[2], (sum(amount)+1)//2)
1
2
3
4
5
6
7
8

impl Solution {
    pub fn fill_cups(amount: Vec<i32>) -> i32 {
        let mut a = amount.clone();
        a.sort();
        let sum = a.iter().sum::<i32>();
        a[2].max((sum+1)/2)
    }
}
1
2
3
4
5
6
7

class Solution {
    fillCups(amount: number[]): number {
        amount.sort((a, b) => a - b);
        const sum = amount[0] + amount[1] + amount[2];
        return Math.max(amount[2], Math.floor((sum+1)/2));
    }
}

Complexity

  • ⏰ Time complexity: O(1)
    • Only a few operations and sorting a fixed-size array.
  • 🧺 Space complexity: O(1)
    • Only a few variables used.