Find the Minimum Amount of Time to Brew Potions
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.
Examples
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.lengthm == mana.length1 <= n, m <= 50001 <= mana[i], skill[i] <= 5000
Solution
Method 1 – Start-Time DP via Prefix Skills
Intuition
Potions must be brewed "in order" while each individual potion flows continuously through all wizards without ever waiting between wizards. Different potions may overlap (pipeline effect) but you may not allow a potion to sit idle waiting for a busy downstream wizard. That condition means: when potion j arrives at wizard i, that wizard must already be free (i.e., finished potion j-1). Therefore we must pick a start time S_j for each potion so that every handoff along its path is wait‑free.
Let pref[i] = skill[0] + ... + skill[i]. Processing time of potion j on wizard i is skill[i] * mana[j]. If potion j starts at S_j, the time it reaches wizard i (start at wizard i) is:
arrival_j(i) = S_j + pref[i-1] * mana[j] (define pref[-1] = 0).
Wizard i finishes potion j-1 at: finish_{j-1}(i) = S_{j-1} + pref[i] * mana[j-1] (because potion j-1 also flowed contiguously).
To avoid waiting: arrival_j(i) >= finish_{j-1}(i) for all i.
So for each wizard i we need:
S_j + pref[i-1] * mana[j] >= S_{j-1} + pref[i] * mana[j-1]
Rearrange:
S_j >= S_{j-1} + pref[i] * mana[j-1] - pref[i-1] * mana[j]
Taking the maximum over all i gives the tightest feasible start time:
S_j = S_{j-1} + max_{0 <= i < n} ( pref[i] * mana[j-1] - pref[i-1] * mana[j] ) with pref[-1]=0.
Base: S_0 = 0. Total completion time after last potion m-1 is:
Answer = S_{m-1} + pref[n-1] * mana[m-1].
Edge cases: if m = 1, answer is simply pref[n-1] * mana[0].
This matches the sample (see derived deltas in commentary) and fixes earlier incorrect formulations that allowed mid-potion waiting or mis-initialized the delta by using skill[0] * mana[j] instead of the correct pref[0] * mana[j-1] term.
Approach
- Precompute
pref(lengthn). - Maintain running start time
S(initial 0). - For each potion index
jfrom 1..m-1:- Compute
delta = max_i ( pref[i] * mana[j-1] - pref[i-1] * mana[j] )(treatpref[-1]=0). - Set
S += delta.
- Compute
- Return
S + pref[n-1] * mana[m-1].
All arithmetic must be 64-bit.
Pseudocode
pref[0] = skill[0]
for i = 1..n-1: pref[i] = pref[i-1] + skill[i]
S = 0
for j = 1..m-1:
delta = pref[0] * mana[j-1] // i = 0 term (pref[-1] = 0)
for i = 1..n-1:
candidate = pref[i] * mana[j-1] - pref[i-1] * mana[j]
delta = max(delta, candidate)
S += delta
answer = S + pref[n-1] * mana[m-1]
return answer
Code
C++
class Solution {
public:
long long minTime(vector<int>& skill, vector<int>& mana) {
int n = skill.size(), m = mana.size();
vector<long long> pref(n);
pref[0] = skill[0];
for (int i = 1; i < n; ++i) pref[i] = pref[i-1] + skill[i];
if (m == 1) return pref.back() * mana[0];
long long S = 0;
for (int j = 1; j < m; ++j) {
long long delta = pref[0] * 1LL * mana[j-1];
for (int i = 1; i < n; ++i) {
long long cand = pref[i] * 1LL * mana[j-1] - pref[i-1] * 1LL * mana[j];
if (cand > delta) delta = cand;
}
S += delta;
}
return S + pref.back() * mana[m-1];
}
};
Go
func minTime(skill []int, mana []int) int64 {
n, m := len(skill), len(mana)
pref := make([]int64, n)
pref[0] = int64(skill[0])
for i := 1; i < n; i++ { pref[i] = pref[i-1] + int64(skill[i]) }
if m == 1 { return pref[n-1] * int64(mana[0]) }
var S int64 = 0
for j := 1; j < m; j++ {
delta := pref[0] * int64(mana[j-1])
for i := 1; i < n; i++ {
cand := pref[i]*int64(mana[j-1]) - pref[i-1]*int64(mana[j])
if cand > delta { delta = cand }
}
S += delta
}
return S + pref[n-1]*int64(mana[m-1])
}
Java
class Solution {
public long minTime(int[] skill, int[] mana) {
int n = skill.length, m = mana.length;
long[] pref = new long[n];
pref[0] = skill[0];
for (int i = 1; i < n; ++i) pref[i] = pref[i-1] + skill[i];
if (m == 1) return pref[n-1] * mana[0];
long S = 0L; // start time of current potion
for (int j = 1; j < m; ++j) {
long delta = pref[0] * (long) mana[j-1]; // i=0 term (pref[-1]=0)
for (int i = 1; i < n; ++i) {
long cand = pref[i] * (long) mana[j-1] - pref[i-1] * (long) mana[j];
if (cand > delta) delta = cand;
}
S += delta;
}
return S + pref[n-1] * (long) mana[m-1];
}
}
Kotlin
class Solution {
fun minTime(skill: IntArray, mana: IntArray): Long {
val n = skill.size; val m = mana.size
val pref = LongArray(n)
pref[0] = skill[0].toLong()
for (i in 1 until n) pref[i] = pref[i-1] + skill[i]
if (m == 1) return pref[n-1] * mana[0]
var S = 0L
for (j in 1 until m) {
var delta = pref[0] * mana[j-1]
for (i in 1 until n) {
val cand = pref[i] * mana[j-1] - pref[i-1] * mana[j]
if (cand > delta) delta = cand
}
S += delta
}
return S + pref[n-1] * mana[m-1]
}
}
Python
class Solution:
def minTime(self, skill: list[int], mana: list[int]) -> int:
n, m = len(skill), len(mana)
pref = [0]*n
pref[0] = skill[0]
for i in range(1, n):
pref[i] = pref[i-1] + skill[i]
if m == 1:
return pref[-1] * mana[0]
S = 0
for j in range(1, m):
delta = pref[0] * mana[j-1] # i=0 term
for i in range(1, n):
cand = pref[i] * mana[j-1] - pref[i-1] * mana[j]
if cand > delta:
delta = cand
S += delta
return S + pref[-1] * mana[-1]
Rust
impl Solution {
pub fn min_time(skill: Vec<i32>, mana: Vec<i32>) -> i64 {
let n = skill.len(); let m = mana.len();
let mut pref = vec![0i64; n];
pref[0] = skill[0] as i64;
for i in 1..n { pref[i] = pref[i-1] + skill[i] as i64; }
if m == 1 { return pref[n-1] * mana[0] as i64; }
let mut s: i64 = 0;
for j in 1..m {
let mut delta = pref[0] * mana[j-1] as i64;
for i in 1..n {
let cand = pref[i] * mana[j-1] as i64 - pref[i-1] * mana[j] as i64;
if cand > delta { delta = cand; }
}
s += delta;
}
s + pref[n-1] * mana[m-1] as i64
}
}
TypeScript
class Solution {
minTime(skill: number[], mana: number[]): number {
const n = skill.length, m = mana.length;
const pref: number[] = new Array(n);
pref[0] = skill[0];
for (let i = 1; i < n; ++i) pref[i] = pref[i-1] + skill[i];
if (m === 1) return pref[n-1] * mana[0];
let S = 0; // start time accumulator
for (let j = 1; j < m; ++j) {
let delta = pref[0] * mana[j-1];
for (let i = 1; i < n; ++i) {
const cand = pref[i] * mana[j-1] - pref[i-1] * mana[j];
if (cand > delta) delta = cand;
}
S += delta;
}
return S + pref[n-1] * mana[m-1];
}
}
Complexity
- ⏰ Time complexity:
O(n * m)– we examine each wizard for each potion (besides the first) once. - 🧺 Space complexity:
O(n)– prefix array only.