3494. Find the Minimum Amount of Time to Brew Potions
Approach
Simulate brewing; each wizard starts when the previous mana assigned finishes.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
Math problems test number theory, combinatorics, and modular arithmetic. Common tools: GCD/LCM (Euclidean algorithm), prime sieve, modular inverse (Fermat's little theorem), digit manipulation, and bit tricks. Overflow is a key concern in C# — use long when products may exceed 2³¹.
A heap (priority queue) gives O(log n) insert and O(1) peek with O(log n) removal. In C#, use PriorityQueue<TElement, TPriority> (.NET 6+). Classic patterns: top-K elements (min-heap of size K), merge K sorted lists, Dijkstra's shortest path, and median in a stream (two heaps).
// Approach: Simulate brewing; each wizard starts when the previous mana assigned finishes.
// Time: O(n * m) Space: O(n)
public class Solution
{
public long MinTime(int[] skill, int[] mana)
{
long sumSkill = 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)
{
prevPotionDone -= (long)skill[i + 1] * mana[j - 1];
prevWizardDone = Math.Max(prevPotionDone, prevWizardDone - (long)skill[i] * mana[j]);
}
prevWizardDone += sumSkill * mana[j];
}
return prevWizardDone;
}
}