#3494
Medium Algorithms Find the minimum amount of time to brew potions
Array Simulation Prefix Sum
62.7% acceptance
Feb 25, 2026
508
359
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.
Solution
Rust
Time O(n²)
Space O(n)
impl Solution {
pub fn min_time(skill: Vec<i32>, mana: Vec<i32>) -> i64 {
let n = skill.len();
let m = mana.len();
// For each wizard i, time to process potion j is skill[i]*mana[j].
// Potions processed in order j=0..m-1.
// Each potion must flow through wizards 0..n-1 sequentially.
// Wizard i starts potion j at time t[i][j] such that t[0][j] >= t[n-1][j-1] + skill[n-1]*mana[j-1].
// Wait: "must be passed to next wizard immediately" = wizard i+1 starts exactly when wizard i finishes.
// So wizard i finishes potion j at: t[i][j] + skill[i]*mana[j].
// Wizard i+1 must start at: t[i][j] + skill[i]*mana[j].
// => t[i+1][j] = t[i][j] + skill[i]*mana[j].
// Also: wizard i starts potion j only after finishing potion j-1:
// t[i][j] >= t[i][j-1] + skill[i]*mana[j-1].
// Total time = t[n-1][m-1] + skill[n-1]*mana[m-1].
// t[i][j] = max(t[i][j-1] + skill[i]*mana[j-1], t[i-1][j] + skill[i-1]*mana[j])
// but that's for t[i][j] = start time of wizard i on potion j.
// Actually: t[i][j] = max(t[i][j-1] + skill[i]*mana[j-1], t[i-1][j] + skill[i-1]*mana[j])
// This simplifies: dp[j] = start time of the first wizard on potion j.
// Process potion j: wizard 0 starts at max(dp[j-1] + skill[0]*mana[j-1], prev_end_of_pipeline_for_j...
// Wait, let finish[j] = time when wizard n-1 finishes potion j.
// Potion j can only start when:
// 1. Wizard 0 is free (after finishing potion j-1): start[j] >= start[j-1] + skill[0]*mana[j-1]
// 2. Actually the pipeline: start[j] = max(start[j-1] + skill[0]*mana[j-1], earliest time wizard 0 is free for potion j)
// But also, potion j's start is delayed if potion j-1 is still in the pipeline.
// Key insight: potion j starts when wizard 0 is free AND (optional constraint based on pipeline).
// Actually, the constraint is: wizard i starts potion j only after wizard i-1 finishes.
// finish[i][j] = start[i][j] + skill[i]*mana[j].
// start[i][j] = finish[i-1][j] (wizard i starts when i-1 finishes, immediately).
// Also start[0][j] >= finish[0][j-1] = start[0][j-1] + skill[0]*mana[j-1].
// And start[i][j] >= start[i][j-1] + skill[i]*mana[j-1] (wizard i must finish j-1 before starting j).
// Since start[i][j] = finish[i-1][j] = start[i-1][j] + skill[i-1]*mana[j],
// and start[i][j] >= start[i][j-1] + skill[i]*mana[j-1],
// we have start[i][j] = max(start[i-1][j] + skill[i-1]*mana[j], start[i][j-1] + skill[i]*mana[j-1]).
// But start[i][j-1] is known. And start[i-1][j] depends on start[i-1][j-1]... recursive.
// Simplify: track start_potion[j] = start time of wizard 0 on potion j.
// Then: start_potion[j] = max(start_potion[j-1] + skill[0]*mana[j-1],
// finish_of_pipeline[j-1] - sum_of_prefix_skills * mana[j])
// This is complex. Use O(n*m) DP.
// Let dp[j] = start time of wizard 0 on potion j.
let mut dp = vec![0i64; m];
for j in 1..m {
// Wizard 0 finishes j-1 at dp[j-1] + skill[0]*mana[j-1].
// Each subsequent wizard adds their time.
// But we also need wizard 0 to wait until last potion in pipeline finishes.
// Simpler: simulate the pipeline.
dp[j] = dp[j-1] + skill[0] as i64 * mana[j-1] as i64;
}
// Actually, compute the bottleneck differently.
// For each potion, track "pipeline finish time minus cumulative prefix skill".
// Let S[i] = skill[0]+...+skill[i]. Then wizard i finishes potion j at:
// start[i][j] + skill[i]*mana[j] = start[0][j] + S[i]*mana[j].
// Pipeline finish = start[0][j] + S[n-1]*mana[j].
// For potion j: start[0][j] >= pipeline_finish[j-1] - S[n-2]*mana[j]? No...
// Actually start[0][j] must satisfy:
// start[0][j] >= start[0][j-1] + skill[0]*mana[j-1] ... (A) wizard 0 finishes j-1
// start[i][j] = start[0][j] + S_prefix[i-1]*mana[j] >= start[i][j-1] + skill[i]*mana[j-1]
// = start[0][j-1] + S_prefix[i-1]*mana[j-1] + skill[i]*mana[j-1]
// = start[0][j-1] + S_prefix[i]*mana[j-1]
// So: start[0][j] + S_prefix[i-1]*mana[j] >= start[0][j-1] + S_prefix[i]*mana[j-1]
// start[0][j] >= start[0][j-1] + S_prefix[i]*mana[j-1] - S_prefix[i-1]*mana[j]
// = start[0][j-1] + skill[i]*mana[j-1] - S_prefix[i-1]*(mana[j]-mana[j-1])... no
// start[0][j] >= start[0][j-1] + (S_prefix[i]*mana[j-1] - S_prefix[i-1]*mana[j])
// This must hold for all i = 1..n-1.
// start[0][j] >= start[0][j-1] + max over i=1..n-1 of (S[i]*mana[j-1] - S[i-1]*mana[j])
// where S[i] = skill[0]+...+skill[i].
let mut prefix_s = vec![0i64; n + 1];
for i in 0..n { prefix_s[i+1] = prefix_s[i] + skill[i] as i64; }
let mut start0 = vec![0i64; m];
for j in 1..m {
let mut min_start = start0[j-1] + skill[0] as i64 * mana[j-1] as i64; // constraint A
for i in 1..n {
let c = start0[j-1] + prefix_s[i+1] * mana[j-1] as i64 - prefix_s[i] * mana[j] as i64;
if c > min_start { min_start = c; }
}
start0[j] = min_start;
}
start0[m-1] + prefix_s[n] * mana[m-1] as i64
}
}