Watch 10 video solutions for Find the Minimum Amount of Time to Brew Potions, a medium level problem involving Array, Simulation, Prefix Sum. This walkthrough by codestorywithMIK has 11,849 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |