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:
t = 0, and is completed by time t = 3.t = 1, and is completed by time t = 4.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.lengthm == mana.length1 <= n, m <= 50001 <= mana[i], skill[i] <= 5000Problem Overview: You are given an array representing the time or cost required to brew each potion in order. The goal is to compute the minimum total time required to finish brewing all potions while respecting the brewing constraints defined in the problem. Since each decision affects future potions, the solution relies on modeling cumulative progress across the array.
Approach 1: Brute Force Simulation (O(n2) time, O(1) space)
The most direct strategy simulates the brewing process step by step. For every potion i, recompute the total time spent on all previous potions and determine when the current one can start. This requires repeatedly iterating over earlier elements, which results in nested loops. While simple to reason about, the repeated recomputation makes this approach quadratic. It is useful only for validating logic or very small inputs.
Approach 2: Prefix Sum Based Simulation (O(n) time, O(n) space)
Instead of recalculating the cumulative brewing time each step, maintain a prefix sum array where prefix[i] stores the total brewing time up to potion i. Each new potion’s start or completion time can then be derived in constant time using these cumulative values. This eliminates repeated work from the brute force approach. Prefix sums are a common optimization for problems involving repeated range totals over an array.
Approach 3: Dynamic Programming (O(n) time, O(n) space)
The optimal implementation models the process with dynamic programming. Define dp[i] as the minimum time needed to finish brewing the first i potions. Each state transitions from the previous state by incorporating the cost of brewing potion i and updating cumulative timing constraints. Prefix sums allow constant‑time computation of the required totals, so each state is processed once. This method combines simulation of the brewing order with cumulative calculations from prefix sum preprocessing, resulting in linear time.
Recommended for interviews: Start by explaining the brute force simulation to show you understand the brewing dependency between potions. Then move to the dynamic programming approach with prefix sums. Interviewers typically expect the O(n) DP solution because it removes redundant work and clearly models the sequential state transition.
We define f[i] as the time when wizard i completes the previous potion.
For the current potion x, we need to calculate the completion time for each wizard. Let tot represent the completion time of the current potion, initially tot = 0.
For each wizard i, the time he starts processing the current potion is max(tot, f[i]), and the time required to process this potion is skill[i] times mana[x]. Therefore, the time he completes this potion is max(tot, f[i]) + skill[i] times mana[x]. We update tot to this value.
Since the brewing process requires that the potion must be immediately passed to the next wizard and processing must start immediately after the current wizard completes their work, we need to update the completion time f[i] for each wizard's previous potion. For the last wizard n-1, we directly update f[n-1] to tot. For other wizards i, we can update f[i] by traversing in reverse order, specifically, f[i] = f[i+1] - skill[i+1] times mana[x].
Finally, f[n-1] is the minimum total time required to complete brewing all potions.
The time complexity is O(n times m) and the space complexity is O(n), where n and m are the number of wizards and potions respectively.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Simulation | O(n^2) | O(1) | For understanding the process or verifying logic on small inputs |
| Prefix Sum Simulation | O(n) | O(n) | When repeated cumulative calculations appear in array processing |
| Dynamic Programming | O(n) | O(n) | Preferred solution for interviews and large constraints |
Find the Minimum Amount of Time to Brew Potions | Deep Dive | Leetcode 3494 | codestorywithMIK • codestorywithMIK • 11,849 views views
Watch 9 more video solutions →Practice Find the Minimum Amount of Time to Brew Potions with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor