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

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 – Prefix Sum Optimization

Intuition

We need to find the minimum time for m potions to be brewed sequentially by n wizards, where each wizard processes each potion in order. Each wizard i takes skill[i] * mana[j] time for potion j, and synchronization means a wizard must wait for the previous wizard to finish before starting. The goal is to efficiently compute the total brewing time using a prefix sum array (skillSum) to track cumulative skill and minimize waiting time.

Approach

  1. Compute prefix sums of skill in an array skillSum, where skillSum[i] = sum(skill[0] ... skill[i]).
  2. Start with the time for the first potion: skill[0] * mana[0].
  3. For each subsequent potion:
    • For each wizard, calculate the maximum additional time needed using skillSum and mana.
    • Accumulate this maximum into the total time.
  4. Add the time for the last wizard to finish the last potion: skillSum[n-1] * mana[m-1].
  5. Return the total brewing time.

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> skillSum(n);
        skillSum[0] = skill[0];
        for (int i = 1; i < n; ++i)
            skillSum[i] = skillSum[i - 1] + skill[i];
        long long totalTime = skill[0] * 1LL * mana[0];
        for (int j = 1; j < m; ++j) {
            long long maxWait = skill[0] * 1LL * mana[j];
            for (int i = 1; i < n; ++i) {
                long long wait = skillSum[i] * mana[j - 1] - skillSum[i - 1] * mana[j];
                if (wait > maxWait) maxWait = wait;
            }
            totalTime += maxWait;
        }
        return totalTime + skillSum[n - 1] * mana[m - 1];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

func minTime(skill []int, mana []int) int64 {
    n, m := len(skill), len(mana)
    skillSum := make([]int64, n)
    skillSum[0] = int64(skill[0])
    for i := 1; i < n; i++ {
        skillSum[i] = skillSum[i-1] + int64(skill[i])
    }
    totalTime := int64(skill[0]) * int64(mana[0])
    for j := 1; j < m; j++ {
        maxWait := int64(skill[0]) * int64(mana[j])
        for i := 1; i < n; i++ {
            wait := skillSum[i]*int64(mana[j-1]) - skillSum[i-1]*int64(mana[j])
            if wait > maxWait {
                maxWait = wait
            }
        }
        totalTime += maxWait
    }
    return totalTime + skillSum[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[] skillSum = new long[n];
        skillSum[0] = skill[0];
        for (int i = 1; i < n; ++i)
            skillSum[i] = skillSum[i - 1] + skill[i];
        long totalTime = skill[0] * 1L * mana[0];
        for (int j = 1; j < m; ++j) {
            long maxWait = skill[0] * 1L * mana[j];
            for (int i = 1; i < n; ++i) {
                long wait = skillSum[i] * mana[j - 1] - skillSum[i - 1] * mana[j];
                if (wait > maxWait) maxWait = wait;
            }
            totalTime += maxWait;
        }
        return totalTime + skillSum[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 {
    fun minTime(skill: IntArray, mana: IntArray): Long {
        val n = skill.size; val m = mana.size
        val skillSum = LongArray(n)
        skillSum[0] = skill[0].toLong()
        for (i in 1 until n) skillSum[i] = skillSum[i-1] + skill[i]
        var totalTime = skill[0].toLong() * mana[0]
        for (j in 1 until m) {
            var maxWait = skill[0].toLong() * mana[j]
            for (i in 1 until n) {
                val wait = skillSum[i] * mana[j-1] - skillSum[i-1] * mana[j]
                if (wait > maxWait) maxWait = wait
            }
            totalTime += maxWait
        }
        return totalTime + skillSum[n-1] * mana[m-1]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def minTime(self, skill: list[int], mana: list[int]) -> int:
        n, m = len(skill), len(mana)
        skillSum = [skill[0]] + [0]*(n-1)
        for i in range(1, n):
            skillSum[i] = skillSum[i-1] + skill[i]
        totalTime = skill[0] * mana[0]
        for j in range(1, m):
            maxWait = skill[0] * mana[j]
            for i in range(1, n):
                wait = skillSum[i] * mana[j-1] - skillSum[i-1] * mana[j]
                if wait > maxWait:
                    maxWait = wait
            totalTime += maxWait
        return totalTime + skillSum[n-1] * mana[m-1]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

impl Solution {
    pub fn min_time(skill: Vec<i32>, mana: Vec<i32>) -> i64 {
        let n = skill.len(); let m = mana.len();
        let mut skill_sum = vec![0i64; n];
        skill_sum[0] = skill[0] as i64;
        for i in 1..n {
            skill_sum[i] = skill_sum[i-1] + skill[i] as i64;
        }
        let mut total_time = skill[0] as i64 * mana[0] as i64;
        for j in 1..m {
            let mut max_wait = skill[0] as i64 * mana[j] as i64;
            for i in 1..n {
                let wait = skill_sum[i] * mana[j-1] as i64 - skill_sum[i-1] * mana[j] as i64;
                if wait > max_wait {
                    max_wait = wait;
                }
            }
            total_time += max_wait;
        }
        total_time + skill_sum[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

class Solution {
    minTime(skill: number[], mana: number[]): number {
        const n = skill.length, m = mana.length;
        const skillSum: number[] = Array(n).fill(0);
        skillSum[0] = skill[0];
        for (let i = 1; i < n; ++i) skillSum[i] = skillSum[i-1] + skill[i];
        let totalTime = skill[0] * mana[0];
        for (let j = 1; j < m; ++j) {
            let maxWait = skill[0] * mana[j];
            for (let i = 1; i < n; ++i) {
                const wait = skillSum[i] * mana[j-1] - skillSum[i-1] * mana[j];
                if (wait > maxWait) maxWait = wait;
            }
            totalTime += maxWait;
        }
        return totalTime + skillSum[n-1] * mana[m-1];
    }
}

Complexity

  • ⏰ Time complexity: O(n*m) — We iterate through all n wizards for each of the m potions.
  • 🧺 Space complexity: O(n) — We store the prefix sum in skillSum, requiring an array of size n