Skip to content

3494. Find the Minimum Amount of Time to Brew Potions

  • Time: $O(nm)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
 public:
  long long minTime(vector<int>& skill, vector<int>& mana) {
    long sumSkill = accumulate(skill.begin(), skill.end(), 0L);
    long prevWizardDone = sumSkill * mana[0];

    for (int j = 1; j < mana.size(); ++j) {
      long prevPotionDone = prevWizardDone;
      for (int i = skill.size() - 2; i >= 0; --i) {
        // start time for wizard i brewing potion j
        // = max(end time for wizard i brewing potion j - 1,
        //       the earliest start time for wizard i + 1 brewing potion j
        //       (coming from previous iteration)
        //       - time for wizard i brewing potion j)
        prevPotionDone -= static_cast<long>(skill[i + 1]) * mana[j - 1];
        prevWizardDone =
            max(prevPotionDone,
                prevWizardDone - static_cast<long>(skill[i]) * mana[j]);
      }
      prevWizardDone += sumSkill * mana[j];
    }

    return prevWizardDone;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
  public long minTime(int[] skill, int[] mana) {
    long sumSkill = Arrays.stream(skill).sum();
    long prevWizardDone = sumSkill * mana[0];

    for (int j = 1; j < mana.length; ++j) {
      long prevPotionDone = prevWizardDone;
      for (int i = skill.length - 2; i >= 0; --i) {
        // start time for wizard i brewing potion j
        // = max(end time for wizard i brewing potion j - 1,
        //       the earliest start time for wizard i + 1 brewing potion j
        //       (coming from previous iteration)
        //       - time for wizard i brewing potion j)
        prevPotionDone -= (long) skill[i + 1] * mana[j - 1];
        prevWizardDone = Math.max(prevPotionDone, prevWizardDone - (long) skill[i] * mana[j]);
      }
      prevWizardDone += sumSkill * mana[j];
    }

    return prevWizardDone;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
  def minTime(self, skill: list[int], mana: list[int]) -> int:
    sumSkill = sum(skill)
    prevWizardDone = sumSkill * mana[0]

    for j in range(1, len(mana)):
      prevPotionDone = prevWizardDone
      for i in range(len(skill) - 2, -1, -1):
        # start time for wizard i brewing potion j
        # = max(end time for wizard i brewing potion j - 1,
        #       the earliest start time for wizard i + 1 brewing potion j
        #       (coming from previous iteration)
        #       - time for wizard i brewing potion j)
        prevPotionDone -= skill[i + 1] * mana[j - 1]
        prevWizardDone = max(prevPotionDone,
                             prevWizardDone - skill[i] * mana[j])
      prevWizardDone += sumSkill * mana[j]

    return prevWizardDone