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

1
2

Input: skill = [1,5,2,4], mana = [5,1,4,2]
Output: 110

Explanation:

Potion NumberStart timeWizard 0 done byWizard 1 done byWizard 2 done byWizard 3 done by
005304060
15253586064
254587886102
3868898102110

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

1
2
3
4
5
6

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

1
2

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

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

  1. Precompute pref (length n).
  2. Maintain running start time S (initial 0).
  3. For each potion index j from 1..m-1:
    • Compute delta = max_i ( pref[i] * mana[j-1] - pref[i-1] * mana[j] ) (treat pref[-1]=0).
    • Set S += delta.
  4. Return S + pref[n-1] * mana[m-1].

All arithmetic must be 64-bit.

Pseudocode

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

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];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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])
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

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];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

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]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

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]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

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.