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

This approach optimizes the O(n*m) solution by recognizing that the inner loop's computation is a geometric query that can be solved more efficiently. The calculation of the delay term for each potion, max_{i} (a * P_i - b * P_{i-1}), is equivalent to finding an extreme point on a set of 2D points. By pre-processing these points to build their convex hull, we can answer each query in logarithmic time instead of linear time. This technique is often called the Convex Hull Trick.

Algorithm

The problem is the same as in the previous approach, but we focus on optimizing the calculation of C_j = max_{i=0..n-1} (mana[j-1] * P_i - mana[j] * P_{i-1}).
Let a = mana[j-1] and b = mana[j]. We want to maximize a * P_i - b * P_{i-1}.
Define a set of 2D points (x_i, y_i) = (P_{i-1}, P_i) for i=0..n-1, where P_{-1}=0. The problem is now to find a point in this set that maximizes a*y - b*x.
This is a classic computational geometry problem. The point that maximizes such a linear expression must lie on the convex hull of the set of points. Specifically, it will be on the upper convex hull.
First, compute the prefix sums P and generate the points (P_{i-1}, P_i). Since the x-coordinates (P_{i-1}) are sorted, we can build the upper convex hull in O(n) time using a monotone chain algorithm.
For each potion j from 1 to m-1, we have a query. The expression a*y - b*x = k corresponds to a line y = (b/a)x + k/a. We want to find the point on the hull that is touched by a line with slope q = b/a that has the maximum y-intercept.
The slopes of the edges of the upper convex hull are monotonically decreasing. We can use binary search on the hull vertices to find the optimal vertex for the query slope q in O(log n) time.
The rest of the algorithm proceeds as before, but with the O(n) inner loop replaced by an O(log n) query on the convex hull.

Walkthrough

We transform the algebraic problem of finding the maximum of a set of linear expressions into a geometric one. The key steps are:

Point Generation: As in the previous approach, compute prefix sums P of skill. Then, create n points of the form (P_{i-1}, P_i). Note that P_{-1}=0.
Convex Hull Construction: Build the upper convex hull of these n points. Since the points are already sorted by their x-coordinate (P_{i-1} is non-decreasing), this can be done in O(n) time using a standard algorithm like the monotone chain scan.
Querying: For each potion j from 1 to m-1, we need to find the point (x, y) on the hull that maximizes mana[j-1]*y - mana[j]*x. The function f(k) = mana[j-1]*y_k - mana[j]*x_k where (x_k, y_k) is the k-th vertex of the hull, is bitonic (it increases to a maximum then decreases). We can find this maximum value using binary search on the hull vertices in O(log n) time.
Aggregation: Sum up the delays to find the start time of the last potion and compute the final answer.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    static class Point {6        long x, y;7        Point(long x, long y) {8            this.x = x;9            this.y = y;10        }11    }12 13    // Returns positive if counter-clockwise, negative if clockwise, 0 if collinear14    private long crossProduct(Point a, Point b, Point c) {15        return (b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x);16    }17 18    public long minimumTime(int[] skill, int[] mana) {19        int n = skill.length;20        int m = mana.length;21 22        long[] p = new long[n];23        p[0] = skill[0];24        for (int i = 1; i < n; i++) {25            p[i] = p[i-1] + skill[i];26        }27 28        List<Point> points = new ArrayList<>();29        points.add(new Point(0, p[0])); // i=0 case: (P_{-1}, P_0)30        for (int i = 1; i < n; i++) {31            points.add(new Point(p[i-1], p[i]));32        }33 34        // Build upper convex hull35        List<Point> hull = new ArrayList<>();36        for (Point pt : points) {37            while (hull.size() >= 2 && crossProduct(hull.get(hull.size() - 2), hull.get(hull.size() - 1), pt) <= 0) {38                hull.remove(hull.size() - 1);39            }40            hull.add(pt);41        }42 43        long currentS = 0;44        for (int j = 1; j < m; j++) {45            long a = mana[j-1];46            long b = mana[j];47 48            // Binary search on the hull to find the optimal point49            int low = 0, high = hull.size() - 1;50            int opt_idx = 0;51            while (low <= high) {52                int mid1 = low + (high - low) / 3;53                int mid2 = high - (high - low) / 3;54                long val1 = a * hull.get(mid1).y - b * hull.get(mid1).x;55                long val2 = a * hull.get(mid2).y - b * hull.get(mid2).x;56                if (val1 < val2) {57                    low = mid1 + 1;58                } else {59                    high = mid2 - 1;60                }61            }62            opt_idx = low;63            long max_term = a * hull.get(opt_idx).y - b * hull.get(opt_idx).x;64 65            if (max_term > 0) {66                currentS += max_term;67            }68        }69 70        return currentS + (long)mana[m-1] * p[n-1];71    }72}

Complexity

Time

O(n + m log n) `O(n)` is needed for computing prefix sums and building the convex hull. Afterwards, for each of the `m-1` potions, we perform a query on the hull. Since the query is done via binary search on the hull vertices (of which there are at most `n`), each query takes `O(log n)` time.

Space

O(n) Space is required for the prefix sums `P`, the list of points, and the vertices of the convex hull. All are proportional to `n`.

Trade-offs

Pros

Highly efficient, with a time complexity that is near-linear in n+m.
It is the optimal solution for the given problem constraints.

Cons

The implementation is significantly more complex, requiring knowledge of computational geometry algorithms like building a convex hull and querying it.
The logic for binary searching on the hull can be tricky to get right.

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