Minimum Amount of Time to Fill Cups

Easy
840.

Minimum Amount of Time to Fill Cups

Minimum Amount of Time to Fill Cups is an easy coding problem on arrays, math and greedy, asked in Amazon, Google and Infosys interviews.

A water dispenser offers cold, warm and hot water. Each second you may fill either two cups of different types or one cup of any type.

Given amount = [cold, warm, hot], return the minimum number of seconds to fill all the cups.

Example 1

Input
amount = [1,4,2]
Output
4
Explanation
Pair the 4 warm cups with the others, then finish alone.

Example 2

Input
amount = [5,4,4]
Output
7
Explanation
The total is 13, and ceil(13 / 2) is 7.

Example 3

Input
amount = [5,0,0]
Output
5
Explanation
One type only, so no pairing is possible.

Constraints

  • amount.length == 3
  • 0 <= amount[i] <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} amount
 * @return {number}
 */
var fillCups = function(amount) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Amount of Time to Fill Cups — Problem & Solution

Minimum Amount of Time to Fill Cups solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Minimum Amount of Time to Fill Cups is an easy coding problem on arrays, math and greedy, asked in Amazon, Google and Infosys interviews.

  • Difficulty: Easy
  • Topics: Arrays, Math, Greedy, Heap
  • Asked at: Amazon, Google, Infosys
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A water dispenser offers cold, warm and hot water. Each second you may fill either two cups of different types or one cup of any type.

Given amount = [cold, warm, hot], return the minimum number of seconds to fill all the cups.

Example 1

Input: amount = [1,4,2]
Output: 4
Explanation: Pair the 4 warm cups with the others, then finish alone.

Example 2

Input: amount = [5,4,4]
Output: 7
Explanation: The total is 13, and ceil(13 / 2) is 7.

Example 3

Input: amount = [5,0,0]
Output: 5
Explanation: One type only, so no pairing is possible.

Constraints

  • amount.length == 3
  • 0 <= amount[i] <= 100

Hints for Minimum Amount of Time to Fill Cups

  1. Hint 1

    Two lower bounds apply: the largest single count, and half the total rounded up.

  2. Hint 2

    The answer is the larger of the two.

  3. Hint 3

    Pairing the two largest remaining counts each second achieves it.

How to solve Minimum Amount of Time to Fill Cups

Two obvious lower bounds turn out to be jointly sufficient. Each second fills at most two cups, so at least ceil(total / 2) seconds are needed; and the largest type needs at least its own count of seconds, since two cups of the same type cannot be filled together.

Approach

  1. Sort the three counts descending.
  2. Return max(largest, ceil(total / 2)).

Why it works

If the largest count exceeds the other two combined, every second must include one cup of that type, so its count is the answer. Otherwise the counts can be paired down two at a time — always pairing the two largest remaining keeps them balanced enough that no type is ever left stranded — and ceil(total / 2) seconds suffice.

Complexity

  • Time — O(1)
  • Space — O(1)

Pitfalls

  • Taking only ceil(total / 2) fails on inputs like [5,0,0].
  • Taking only the maximum fails on [5,4,4].
  • Integer division must round up: (total + 1) / 2.

Reference solution

Python

from typing import List

def fillCups(amount: List[int]) -> int:
    a = sorted(amount, reverse=True)
    total = sum(a)
    return max(a[0], (total + 1) // 2)

Java

public static int fillCups(int[] amount) {
    int[] a = amount.clone();
    Arrays.sort(a);
    int total = a[0] + a[1] + a[2];
    return Math.max(a[2], (total + 1) / 2);
}

C++

int fillCups(vector<int>& amount) {
    vector<int> a = amount;
    sort(a.begin(), a.end());
    int total = a[0] + a[1] + a[2];
    return max(a[2], (total + 1) / 2);
}

JavaScript

var fillCups = function(amount) {
    var a = amount.slice().sort(function(x, y) { return y - x; });
    var total = a[0] + a[1] + a[2];
    return Math.max(a[0], Math.floor((total + 1) / 2));
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Greedy Algorithms