Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

A potion cannot wait between wizards, so choosing its start time fixes every later handoff. For each wizard, that start time must be late enough that the previous potion has finished there when the current potion arrives. The tightest of these constraints determines the earliest feasible start.

Approach

Maintain the previous potion's completion time at each wizard, initially zero. For the current potion, scan wizards while accumulating its processing time before each wizard. Its required start offset at wizard i is previousFinish[i] - timeBefore[i]; retain the maximum of these offsets and zero.

During the same scan, store the current potion's cumulative durations through each wizard. After finding the maximum offset, add it to every stored duration to obtain actual completion times. Repeat for all potions and return the last wizard's final completion time.

Each chosen offset is both necessary for some wizard and sufficient for every wizard. Starting a potion later cannot help subsequent potions finish earlier, so using these earliest feasible starts is optimal.

class Solution:
    def minTime(self, skill: List[int], mana: List[int]) -> int:
        n = len(skill)
        m = len(mana)
        prev = [0] * n

        for j in range(m):
            mx = 0
            t = 0
            for i in range(n):
                mx = max(mx, prev[i] - t)
                t += skill[i] * mana[j]
                prev[i] = t

            for k in range(n):
                prev[k] += mx

        return prev[-1]

Complexity analysis

Let w = skill.length and p = mana.length. Time: O(w * p). Auxiliary space: O(w).