3494. Find the Minimum Amount of Time to Brew Potions LeetCode Solution

Last updated: March 24, 2025

In this guide, you will get 3494. Find the Minimum Amount of Time to Brew Potions LeetCode Solution with the best time and space complexity. The solution to Find the Minimum Amount of Time to Brew Potions problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Find the Minimum Amount of Time to Brew Potions solution in C++
Find the Minimum Amount of Time to Brew Potions solution in Java
Find the Minimum Amount of Time to Brew Potions solution in Python
Additional Resources

3494. Find the Minimum Amount of Time to Brew Potions LeetCode Solution image

Problem Statement of Find the Minimum Amount of Time to Brew Potions

You are given two integer arrays, skill and mana, of length n and m, respectively.
In a laboratory, n wizards must brew m potions in order. Each potion has a mana capacity mana[j] and must pass through all the wizards sequentially to be brewed properly. The time taken by the ith wizard on the jth potion is timeij = skill[i] * mana[j].
Since the brewing process is delicate, a potion must be passed to the next wizard immediately after the current wizard completes their work. This means the timing must be synchronized so that each wizard begins working on a potion exactly when it arrives.
Return the minimum amount of time required for the potions to be brewed properly.

Example 1:

Input: skill = [1,5,2,4], mana = [5,1,4,2]
Output: 110
Explanation:

Potion Number
Start time
Wizard 0 done by
Wizard 1 done by
Wizard 2 done by
Wizard 3 done by

0
0
5
30
40
60

1
52
53
58
60
64

2
54
58
78
86
102

3
86
88
98
102
110

As an example for why wizard 0 cannot start working on the 1st potion before time t = 52, consider the case where the wizards started preparing the 1st potion at time t = 50. At time t = 58, wizard 2 is done with the 1st potion, but wizard 3 will still be working on the 0th potion till time t = 60.

Example 2:

Input: skill = [1,1,1], mana = [1,1,1]
Output: 5
Explanation:

Preparation of the 0th potion begins at time t = 0, and is completed by time t = 3.
Preparation of the 1st potion begins at time t = 1, and is completed by time t = 4.
Preparation of the 2nd potion begins at time t = 2, and is completed by time t = 5.

Example 3:

Input: skill = [1,2,3,4], mana = [1,2]
Output: 21

Constraints:

n == skill.length
m == mana.length
1 <= n, m <= 5000
1 <= mana[i], skill[i] <= 5000

Complexity Analysis

Time Complexity: O(nm)
Space Complexity: O(1)

3494. Find the Minimum Amount of Time to Brew Potions LeetCode Solution in C++

class Solution {
 public:
  long long minTime(vector<int>& skill, vector<int>& mana) {
    long sumSkill = accumulate(skill.begin(), skill.end(), 0L);
    long prevWizardDone = sumSkill * mana[0];

    for (int j = 1; j < mana.size(); ++j) {
      long prevPotionDone = prevWizardDone;
      for (int i = skill.size() - 2; i >= 0; --i) {
        // start time for wizard i brewing potion j
        // = max(end time for wizard i brewing potion j - 1,
        //       the earliest start time for wizard i + 1 brewing potion j
        //       (coming from previous iteration)
        //       - time for wizard i brewing potion j)
        prevPotionDone -= static_cast<long>(skill[i + 1]) * mana[j - 1];
        prevWizardDone =
            max(prevPotionDone,
                prevWizardDone - static_cast<long>(skill[i]) * mana[j]);
      }
      prevWizardDone += sumSkill * mana[j];
    }

    return prevWizardDone;
  }
};
/* code provided by PROGIEZ */

3494. Find the Minimum Amount of Time to Brew Potions LeetCode Solution in Java

class Solution {
  public long minTime(int[] skill, int[] mana) {
    long sumSkill = Arrays.stream(skill).sum();
    long prevWizardDone = sumSkill * mana[0];

    for (int j = 1; j < mana.length; ++j) {
      long prevPotionDone = prevWizardDone;
      for (int i = skill.length - 2; i >= 0; --i) {
        // start time for wizard i brewing potion j
        // = max(end time for wizard i brewing potion j - 1,
        //       the earliest start time for wizard i + 1 brewing potion j
        //       (coming from previous iteration)
        //       - time for wizard i brewing potion j)
        prevPotionDone -= (long) skill[i + 1] * mana[j - 1];
        prevWizardDone = Math.max(prevPotionDone, prevWizardDone - (long) skill[i] * mana[j]);
      }
      prevWizardDone += sumSkill * mana[j];
    }

    return prevWizardDone;
  }
}
// code provided by PROGIEZ

3494. Find the Minimum Amount of Time to Brew Potions LeetCode Solution in Python

class Solution:
  def minTime(self, skill: list[int], mana: list[int]) -> int:
    sumSkill = sum(skill)
    prevWizardDone = sumSkill * mana[0]

    for j in range(1, len(mana)):
      prevPotionDone = prevWizardDone
      for i in range(len(skill) - 2, -1, -1):
        # start time for wizard i brewing potion j
        # = max(end time for wizard i brewing potion j - 1,
        #       the earliest start time for wizard i + 1 brewing potion j
        #       (coming from previous iteration)
        #       - time for wizard i brewing potion j)
        prevPotionDone -= skill[i + 1] * mana[j - 1]
        prevWizardDone = max(prevPotionDone,
                             prevWizardDone - skill[i] * mana[j])
      prevWizardDone += sumSkill * mana[j]

    return prevWizardDone
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents