We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Minimum Amount of Time to Brew Potions

Number: 3794

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

We are given two arrays: one representing the skill levels of n wizards and the other representing the mana capacities of m potions. Each potion must be brewed by all wizards in order. The time taken by the i-th wizard to brew the j-th potion is given by skill[i] * mana[j]. In addition, as soon as a wizard finishes brewing a potion, the potion must be immediately passed to the next wizard. This means that the start time for any wizard working on a potion is determined by both when the previous wizard finished the same potion and when the current wizard finished the previous potion. The goal is to determine the minimum total time required to brew all m potions following these synchronized constraints.

Key Insights

  • The brewing process can be viewed as a pipeline where each potion passes sequentially through all wizards.
  • For any potion j and wizard i, the start time is constrained by the finish time of wizard i on the previous potion (j-1) and by the finish time of the previous wizard (i-1) on the current potion.
  • The recurrence relation becomes: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + (skill[i] * mana[j]).
  • The extreme cases (first potion and first wizard) can be computed directly and then the rest of the table can be filled using dynamic programming.
  • This dynamic programming formulation resembles computing a “max‐cost” path in a 2D grid, where the cost addition is based on the product of corresponding wizard skill and potion mana.

Space and Time Complexity

Time Complexity: O(n * m)
Space Complexity: O(m) (using space optimization by storing only one row at a time)

Solution

To solve the problem we use dynamic programming. We define dp[i][j] as the minimum finish time when the i-th wizard has completed potion j. The recurrence is:

 • For the first wizard: dp[0][j] = dp[0][j-1] + (skill[0] * mana[j]), since the wizard processes potions sequentially.
 • For the first potion across wizards: dp[i][0] = dp[i-1][0] + (skill[i] * mana[0]).
 • For any other cell (i, j): dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + (skill[i] * mana[j]).

This recurrence captures the constraint that a wizard can start brewing potion j only after both the previous wizard has finished potion j and the current wizard has finished potion j-1. The final answer is dp[n-1][m-1]. To optimize space, we can use a one-dimensional array (or two rows) since each row depends only on the previous row and the current row’s previous value.

Code Solutions

# Python solution using dynamic programming with space optimization

def minBrewTime(skill, mana):
    n = len(skill)
    m = len(mana)
    
    # dp represents the current row of finish times for each potion for the current wizard.
    dp = [0] * m
    
    # Base for first wizard (i == 0): successive accumulation of potion brew times.
    dp[0] = skill[0] * mana[0]
    for j in range(1, m):
        dp[j] = dp[j-1] + skill[0] * mana[j]
    
    # Process subsequent wizards.
    for i in range(1, n):
        # For the current wizard, first potion finish time.
        dp[0] = dp[0] + skill[i] * mana[0]
        for j in range(1, m):
            # The current wizard can start potion j only after:
            #   - the previous wizard has finished potion j (dp[j] from previous iteration)
            #   - the current wizard has finished potion j-1 (dp[j-1])
            dp[j] = max(dp[j], dp[j-1]) + skill[i] * mana[j]
    
    return dp[m-1]

# Example usage:
print(minBrewTime([1,5,2,4], [5,1,4,2]))  # Expected output: 110
← Back to All Questions