algoadvance

You are given a 0-indexed integer array amount of length 3 where amount[0], amount[1], and amount[2] represent the number of cold, warm, and hot water cups you need to fill respectively. You can only fill two cups at a time, and it takes 1 second to fill either one or two cups. Return the minimum number of seconds needed to fill all the cups.

Example 1:

Input: amount = [1,4,2]
Output: 4
Explanation: One way to fill the cups is:
Second 1: Fill the 1st and 3rd cup.
Second 2: Fill the 3rd cup.
Second 3: Fill the 2nd cup.
Second 4: Fill the 2nd cup.

Example 2:

Input: amount = [5,4,4]
Output: 7
Explanation: One way to fill the cups is:
Second 1: Fill the 1st and 2nd cup.
Second 2: Fill the 1st and 3rd cup.
Second 3: Fill the 1st and 2nd cup.
Second 4: Fill the 1st and 2nd cup.
Second 5: Fill the 1st and 3rd cup.
Second 6: Fill the 2nd and 3rd cup.
Second 7: Fill the 1st cup.

Example 3:

Input: amount = [5,0,0]
Output: 5
Explanation: Every second, we can only fill the 1st cup.

Clarifying Questions

  1. Can the input array amount contain negative numbers?
    • No, the problem guarantees that the input consists of non-negative integers.
  2. What is the maximum length of the array amount?
    • The problem statement clearly states that the length is always 3.
  3. Can we assume the input will always be valid according to the constraints provided?
    • Yes.

Strategy

  1. Sorting Method:
    • Sort the list to get the three numbers in non-decreasing order.
    • While the largest element is not zero, decrement the two largest elements (to maximize the number of cups filled per second).
    • Remove the zero elements and resort the remaining elements to always work on the two largest elements.
  2. Initial Insight:
    • We can use a more optimal approach without continuously resorting. If we consider the largest number and the sum of the two smaller numbers, the optimal answer appears to be the max value between the largest value and half the sum of the array because:
      • If the largest value is larger than the sum of the other two, the total time will be the largest value because we can fill 2 cups at a time using the smaller values.
      • Otherwise, it’s the combination of their fills balanced by the possibility of filling 2 cups per second.

Code

def fillCups(amount):
    amount.sort()
    # The number of seconds required will be the largest of
    # the maximum value in `amount` or half the sum (rounded up).
    return max(amount[2], (sum(amount) + 1) // 2)

# Test cases
print(fillCups([1, 4, 2]))  # Output: 4
print(fillCups([5, 4, 4]))  # Output: 7
print(fillCups([5, 0, 0]))  # Output: 5

Time Complexity

Space Complexity

The space complexity is also (O(1)) because we are only using a fixed amount of extra space for variables regardless of the input size.

Try our interview co-pilot at AlgoAdvance.com