Find the Minimum Amount of Time to Brew Potions

Med

#3107Time: O(n * m) The algorithm involves pre-calculating prefix sums in `O(n)`. Then, it iterates `m-1` times. Inside this loop, there is another loop that runs `n` times to find the maximum delay term. This results in a total time complexity of `O(n + m*n)`, which simplifies to `O(n*m)`.Space: O(n) We use an array of size `n` to store the prefix sums of the `skill` array.

Patterns

Prefix Sum

Data structures

Array

Prompt

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 i^th wizard on the j^th potion is time_ij = 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 1^st potion before time t = 52, consider the case where the wizards started preparing the 1^st potion at time t = 50. At time t = 58, wizard 2 is done with the 1^st potion, but wizard 3 will still be working on the 0^th potion till time t = 60.

Example 2:

Input: skill = [1,1,1], mana = [1,1,1]

Output: 5

Explanation:

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach is based on dynamic programming principles. We derive a recurrence relation for the optimal start time S_j for each potion j. The key insight is that the entire processing pipeline for a potion might need to be delayed to ensure no wizard is required to work on two potions simultaneously. The optimal delay between potion j-1 and j is determined by finding the most constrained wizard, which requires checking all n wizards. This leads to an O(n) calculation for each of the m potions.

Algorithm

Let S_j be the start time for potion j (when wizard 0 begins). We can assume S_0 = 0.
The time wizard i finishes potion j, finish_time(i, j), can be expressed in terms of S_j and prefix sums of skill. Let P_i = skill[0] + ... + skill[i]. Then finish_time(i, j) = S_j + mana[j] * P_i.
A wizard i must be free to start potion j. This implies that the pipeline for potion j must not overtake the pipeline for potion j-1. This gives the constraint finish_time(i-1, j) >= finish_time(i, j-1) for i > 0, and start_time(0, j) >= finish_time(0, j-1) for i=0.
Substituting the formula for finish_time gives a lower bound for S_j based on S_{j-1}: S_j >= S_{j-1} + max_{i=0..n-1} (mana[j-1] * P_i - mana[j] * P_{i-1}), where P_{-1} is taken as 0.
To minimize total time, we choose the earliest possible start time for each potion. We can compute S_j iteratively: S_j = S_{j-1} + max(0, C_j), where C_j is the max term from the previous step.
First, precompute the prefix sums P of the skill array in O(n) time.
Initialize current_S = 0 (representing S_{j-1}).
Loop j from 1 to m-1. In each iteration: a. Calculate C_j by iterating i from 0 to n-1 and finding the maximum of mana[j-1] * P_i - mana[j] * P_{i-1}. This takes O(n) time. b. Update current_S by adding max(0, C_j).
The final result is the finish time of the last wizard on the last potion, which is S_{m-1} + mana[m-1] * P_{n-1}.

Walkthrough

The core of this method is to find the minimum required start time S_j for each potion j sequentially. We start with S_0 = 0. For each subsequent potion j (from 1 to m-1), we calculate the minimum necessary delay after potion j-1 finishes. This delay is determined by the 'bottleneck' wizard, i.e., the wizard i for whom the constraint finish_time(i-1, j) >= finish_time(i, j-1) imposes the largest delay on S_j relative to S_{j-1}. We iterate through all wizards to find this maximum required delay, update the start time for potion j, and repeat until we have the start time for the last potion. The total time is then easily calculated.

All intermediate products and sums can exceed the capacity of a 32-bit integer, so it's crucial to use 64-bit integers (long in Java) for these calculations to avoid overflow.

1class Solution {2    public long minimumTime(int[] skill, int[] mana) {3        int n = skill.length;4        int m = mana.length;5 6        // Step 1: Compute prefix sums of skill7        long[] p = new long[n];8        p[0] = skill[0];9        for (int i = 1; i < n; i++) {10            p[i] = p[i-1] + skill[i];11        }12 13        long currentS = 0; // This will hold S_{j-1} at the start of the loop14 15        // Step 2: Iterate through potions to find their start times16        for (int j = 1; j < m; j++) {17            long maxTerm = 0;18            // Find the maximum delay term C_j19            for (int i = 0; i < n; i++) {20                long p_i = p[i];21                long p_i_minus_1 = (i == 0) ? 0 : p[i-1];22                long term = (long)mana[j-1] * p_i - (long)mana[j] * p_i_minus_1;23                if (term > maxTerm) {24                    maxTerm = term;25                }26            }27            // Update the start time for the current potion j28            currentS += maxTerm;29        }30 31        // Step 3: Calculate final finish time32        return currentS + (long)mana[m-1] * p[n-1];33    }34}

Complexity

Time

O(n * m) The algorithm involves pre-calculating prefix sums in `O(n)`. Then, it iterates `m-1` times. Inside this loop, there is another loop that runs `n` times to find the maximum delay term. This results in a total time complexity of `O(n + m*n)`, which simplifies to `O(n*m)`.

Space

O(n) We use an array of size `n` to store the prefix sums of the `skill` array.

Trade-offs

Pros

It's a correct and relatively intuitive approach once the underlying dynamic relationship between potion start times is understood.
Easier to implement compared to more optimized geometric approaches.

Cons

The time complexity of O(n*m) might be too slow and result in a 'Time Limit Exceeded' error if both n and m are large (e.g., close to 5000).

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem