Minimum Amount of Time to Fill Cups - Practice Coding Problems

Minimum Amount of Time to Fill Cups - 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
Fill up 1 cup of any type of water

You are given a 0-indexed 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

Return the minimum number of seconds needed to fill up all the cups.

Input & Output

Example 1 — Balanced Distribution

$ Input: amount = [1,4,2]

› Output: 4

💡 Note: Optimal strategy: Fill warm+hot (1 sec) → [1,3,1], Fill warm+hot (1 sec) → [1,2,0], Fill cold+warm (1 sec) → [0,1,0], Fill warm (1 sec) → [0,0,0]. Total: 4 seconds.

Example 2 — One Dominant Type

$ Input: amount = [5,4,4]

› Output: 7

💡 Note: With 5 cold cups, we can pair optimally until other types run out. Cold+warm and cold+hot simultaneously for 4 seconds, then 1 cold cup remains, taking 1 more second. Total: 5 + 2 = 7 seconds.

Example 3 — Equal Amounts

$ Input: amount = [5,0,0]

› Output: 5

💡 Note: Only one type available, so we must fill one cup per second for 5 seconds. No pairing possible.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Array of 3 cup counts: [cold, warm, hot]

Strategy

Fill 2 different types per second when possible

Output

Minimum seconds needed to fill all cups

Key Takeaway

🎯 Key Insight: Always pair the two largest cup counts to minimize total filling time

Asked in

G Google 15 M Microsoft 8 a Amazon 12

The key insight is recognizing this as an optimization problem where we want to maximize simultaneous operations. The optimal approach uses a mathematical formula: if the maximum cup count exceeds the sum of the other two, we're limited by that maximum; otherwise, we can pair optimally and need ceiling of (total sum / 2) seconds. Best approach is Mathematical Formula with Time: O(1), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Mathematical Formula	O(1)	O(1)	Use mathematical insight to calculate result directly without simulation
Simulation Approach	O(S log 3)	O(1)	Simulate the process by repeatedly filling cups until all are done
Greedy with Priority Queue	O(S log 3)	O(1)	Use a max heap to efficiently get the largest amounts for optimal pairing

Mathematical Formula — Algorithm Steps

Step 1: Find the maximum amount among the three types
Step 2: Calculate sum of all amounts
Step 3: If max > sum of other two, return max
Step 4: Otherwise return ceiling of (total sum / 2)

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Maximum

Identify the largest cup count

Compare

Check if max > sum of others

Calculate

Return max or ceiling(total/2)

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int max(int a, int b) {
    return a > b ? a : b;
}

int solution(int* amount) {
    int maxAmount = max(amount[0], max(amount[1], amount[2]));
    int total = amount[0] + amount[1] + amount[2];
    int otherSum = total - maxAmount;
    
    if (maxAmount > otherSum) {
        return maxAmount;
    } else {
        return (total + 1) / 2;  // Ceiling division
    }
}

int main() {
    char line[100];
    fgets(line, sizeof(line), stdin);
    
    int amount[3];
    char *token = strtok(line, "[,]");
    for (int i = 0; i < 3; i++) {
        amount[i] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    int result = solution(amount);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

Only performs constant number of comparisons and arithmetic operations

✓ Linear Growth

Space Complexity

O(1)

Uses only a few variables to store max and sum

✓ Linear Space

32.0K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Mathematical Formula — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler