2025-10-09 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge

Today I have done leetcode's October LeetCoding Challenge with cpp.

October LeetCoding Challenge 9

Description

Find the Minimum Amount of Time to Brew Potions

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

Solution

class Solution {
  using ll = long long;
public:
  long long minTime(vector<int>& skill, vector<int>& mana) {
    int ppl = skill.size();
    vector<ll> lastTime(ppl);
    for(int i = 0; i < ppl; ++i) {
      lastTime[i] = (i ? lastTime[i - 1] : 0) + skill[i] * mana[0];
    }
    // cout << lastTime <<endl;
    int potions = mana.size();
    for(int i = 1; i < potions; ++i) {
      long long beginTime = 0;
      long long spent = 0;
      for(int j = 0; j < ppl; ++j) {
        if(beginTime + spent < lastTime[j]) {
          beginTime = lastTime[j] - spent;
        }
        spent += mana[i] * skill[j];
      }
      
      for(int j = 0; j < ppl; ++j) {
        lastTime[j] = (j ? lastTime[j - 1] : beginTime) + skill[j] * mana[i];
      }
    // cout << lastTime <<endl;
    }
    return lastTime.back();
  }
};

// Accepted
// 744/744 cases passed (455 ms)
// Your runtime beats 56.92 % of cpp submissions
// Your memory usage beats 73.85 % of cpp submissions (45.5 MB)
Algorithm