Problem Statement in English

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 time[i][j] = skill[i] * mana[j].

Each 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.

Approach

We can think of the wizards as units in a pipeline, where each unit has a processing time for each potion.

So if potion 1 finished it’s processing at wizard 1, and is now at wizard 2, then the next potion, i.e, potion 2 can not be given to wizard 2, until potion 1 is done with wizard 2.

Thus, potion x depends on potion x-1 for its start time. This is important.

Each wizard i takes skill[i] * mana[j] time to process potion j.

The easy part is figuring out the base plan - before we have to factor in synchronization. So let’s just do that first. Let’s figure out when each potion can be finished, and then we will adjust for synchronization. A forward pass, and a backward pass. We’ll see why as we go along.

For each potion, a step of its process can start after the max of the previous step of the same potion, and the same step of the previous potion (which needs to have been synchronized for us to use in this calculation).

Wizard 1Wizard 2
Potion 1……
Potion 2…depends on left and above

Now we know at what time the potion will finish at the last wizard. So now we can work backwards and figure out when each potion can start at each wizard, and thus adjust the finish times. This is the backward pass.

Read the code to cement things. It’s using a single list to optimise for space.

Solution in Python


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

        for m in mana:
            finish_time[0] = finish_time[0] + skill[0] * m

            for i in range(1, ls):
                finish_time[i] = max(finish_time[i], finish_time[i - 1]) + skill[i] * m

            for i in reversed(range(ls - 1)):
                work_time = skill[i + 1] * m
                finish_time[i] = finish_time[i + 1] - work_time

        return finish_time[-1]

Complexity

  • Time: $O(m * n)$
    Since we have two nested loops, one iterating over mana of size m and the other iterating over skill of size n.

  • Space: $O(n)$
    Since we store the finish_time array of size n.

Mistakes I Made

I had to look this one up :(

And we are done.