# Find the Minimum Amount of Time to Brew Potions **Difficulty:** MEDIUM [External](https://leetcode.com/problems/find-the-minimum-amount-of-time-to-brew-potions) Canonical: https://scaleengineer.com/dsa/problems/find-the-minimum-amount-of-time-to-brew-potions **Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum) **Data structures:** Array --- ## Problem 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` # Approaches ## Iterative Calculation of Start Times 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. **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. **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). ### Explanation 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. ```java class Solution { public long minimumTime(int[] skill, int[] mana) { int n = skill.length; int m = mana.length; // Step 1: Compute prefix sums of skill long[] p = new long[n]; p[0] = skill[0]; for (int i = 1; i < n; i++) { p[i] = p[i-1] + skill[i]; } long currentS = 0; // This will hold S_{j-1} at the start of the loop // Step 2: Iterate through potions to find their start times for (int j = 1; j < m; j++) { long maxTerm = 0; // Find the maximum delay term C_j for (int i = 0; i < n; i++) { long p_i = p[i]; long p_i_minus_1 = (i == 0) ? 0 : p[i-1]; long term = (long)mana[j-1] * p_i - (long)mana[j] * p_i_minus_1; if (term > maxTerm) { maxTerm = term; } } // Update the start time for the current potion j currentS += maxTerm; } // Step 3: Calculate final finish time return currentS + (long)mana[m-1] * p[n-1]; } } ``` ### Algorithm 1. Let `S_j` be the start time for potion `j` (when wizard 0 begins). We can assume `S_0 = 0`. 2. 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`. 3. 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`. 4. 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. 5. 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. 6. First, precompute the prefix sums `P` of the `skill` array in `O(n)` time. 7. Initialize `current_S = 0` (representing `S_{j-1}`). 8. 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)`. 9. 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}`. ## Convex Hull Optimization 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. **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`. **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. ### Explanation We transform the algebraic problem of finding the maximum of a set of linear expressions into a geometric one. The key steps are: 1. **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`. 2. **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. 3. **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. 4. **Aggregation**: Sum up the delays to find the start time of the last potion and compute the final answer. ```java import java.util.ArrayList; import java.util.List; class Solution { static class Point { long x, y; Point(long x, long y) { this.x = x; this.y = y; } } // Returns positive if counter-clockwise, negative if clockwise, 0 if collinear private long crossProduct(Point a, Point b, Point c) { return (b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x); } public long minimumTime(int[] skill, int[] mana) { int n = skill.length; int m = mana.length; long[] p = new long[n]; p[0] = skill[0]; for (int i = 1; i < n; i++) { p[i] = p[i-1] + skill[i]; } List points = new ArrayList<>(); points.add(new Point(0, p[0])); // i=0 case: (P_{-1}, P_0) for (int i = 1; i < n; i++) { points.add(new Point(p[i-1], p[i])); } // Build upper convex hull List hull = new ArrayList<>(); for (Point pt : points) { while (hull.size() >= 2 && crossProduct(hull.get(hull.size() - 2), hull.get(hull.size() - 1), pt) <= 0) { hull.remove(hull.size() - 1); } hull.add(pt); } long currentS = 0; for (int j = 1; j < m; j++) { long a = mana[j-1]; long b = mana[j]; // Binary search on the hull to find the optimal point int low = 0, high = hull.size() - 1; int opt_idx = 0; while (low <= high) { int mid1 = low + (high - low) / 3; int mid2 = high - (high - low) / 3; long val1 = a * hull.get(mid1).y - b * hull.get(mid1).x; long val2 = a * hull.get(mid2).y - b * hull.get(mid2).x; if (val1 < val2) { low = mid1 + 1; } else { high = mid2 - 1; } } opt_idx = low; long max_term = a * hull.get(opt_idx).y - b * hull.get(opt_idx).x; if (max_term > 0) { currentS += max_term; } } return currentS + (long)mana[m-1] * p[n-1]; } } ``` ### Algorithm 1. 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})`. 2. Let `a = mana[j-1]` and `b = mana[j]`. We want to maximize `a * P_i - b * P_{i-1}`. 3. 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`. 4. 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. 5. 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. 6. 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. 7. 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. 8. 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.