Scale Engineer

Minimum Amount of Time to Fill Cups

Easy
#2127Time: 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.
Patterns
Greedy
Algorithms
Sorting
Data structures
ArrayHeap (Priority Queue)

Prompt

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

3 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

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;    }}

Complexity

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.

Trade-offs

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.

Solutions

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;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem