Skip to main content
Talentd

Find the Minimum Amount of Time to Brew Potions - Solution & Explanation

MediumArraySimulationPrefix Sum10 min readAsked at: Amazon, Microsoft, Goldman Sachs +3
Practice this problem

Problem Statement

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:

  1. Preparation of the 0th potion begins at time t = 0, and is completed by time t = 3.
  2. Preparation of the 1st potion begins at time t = 1, and is completed by time t = 4.
  3. 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

Approach Overview

Problem 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.

Solution

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force SimulationO(n^2)O(1)For understanding the process or verifying logic on small inputs
Prefix Sum SimulationO(n)O(n)When repeated cumulative calculations appear in array processing
Dynamic ProgrammingO(n)O(n)Preferred solution for interviews and large constraints

Video Solution

Find the Minimum Amount of Time to Brew Potions | Deep Dive | Leetcode 3494 | codestorywithMIK • codestorywithMIK • 12,013 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find the Minimum Amount of Time to Brew Potions easy or hard?
The problem is generally categorized as Medium difficulty. The main challenge is recognizing that repeated cumulative calculations can be optimized with prefix sums and dynamic programming. Once the correct state definition is identified, the implementation becomes straightforward.
Find the Minimum Amount of Time to Brew Potions Python/Java solution
The typical implementation uses a DP array and a prefix sum array. Python, Java, C++, Go, and TypeScript solutions all follow the same idea: compute cumulative values, update dp[i] based on previous states, and return the final brewing time after processing all potions.
How to solve Find the Minimum Amount of Time to Brew Potions in O(n)?
Process the potions sequentially and maintain cumulative brewing information using a prefix sum array. Use dynamic programming where dp[i] stores the minimum time needed to brew the first i potions. Each transition uses previously computed cumulative values, allowing constant-time updates and a single pass through the array.
What is the best approach for Find the Minimum Amount of Time to Brew Potions?
The most efficient approach uses dynamic programming combined with prefix sums. Define a DP state that represents the minimum time required to finish brewing the first i potions. Prefix sums allow constant-time calculation of cumulative brewing costs, so each potion is processed once. This results in O(n) time complexity and O(n) space complexity.
Is Find the Minimum Amount of Time to Brew Potions asked at Google/Amazon/Meta?
Problems involving cumulative processing, prefix sums, and dynamic programming frequently appear in interviews at companies like Google, Amazon, and Meta. Variations of scheduling or cumulative cost problems are common because they test array reasoning and state transition design.
What data structure is used in Find the Minimum Amount of Time to Brew Potions?
The solution primarily uses arrays for prefix sums and dynamic programming states. These structures store cumulative brewing times and intermediate results so the algorithm can update values in constant time while iterating through the potions.
What is the time complexity of Find the Minimum Amount of Time to Brew Potions?
The optimal solution runs in O(n) time where n is the number of potions. Each potion is processed once while computing cumulative totals using prefix sums. Space complexity is typically O(n) for the DP or prefix array used to store intermediate results.

Ready to solve this problem?

Practice Find the Minimum Amount of Time to Brew Potions with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays