Tejav
#3494

Find the Minimum Amount of Time to Brew Potions

Medium
ArraySimulationPrefix SumPrefix SumDynamic Programming
LeetCode ↗

Approaches

Brute ForceOptimal
Complexity Comparison
Brute ForceOptimal Solution★
Time
O(n²)
O(n)
Space
O(1)
O(n)
💡

Intuition

Time O(n)Space O(n)

Utilize a prefix sum approach to track the earliest free time for each wizard, minimizing redundant calculations.

⚙️

Algorithm

3 steps
  1. 1Step 1: Initialize an array to track the earliest free time for each wizard.
  2. 2Step 2: For each potion, calculate the time taken by each wizard based on their skill and the potion's mana.
  3. 3Step 3: Update the free time for each wizard and return the total time for the last wizard.
solution.py9 lines
1def minTime(skill, mana):
2    n, m = len(skill), len(mana)
3    f = [0] * n
4    for j in range(m):
5        now = f[0]
6        for i in range(n):
7            now = max(now + skill[i] * mana[j], f[i])
8            f[i] = now
9    return now
ℹ

Complexity note: The complexity is linear due to a single pass through the wizards for each potion, leveraging previous results.

  • 1Understanding the sequential nature of the problem helps in optimizing the brewing time.
  • 2Tracking the earliest free time for each wizard allows for efficient calculations.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.