LeetCode Problem 3494

Difficulty: 🟡 Medium
Topics: Array, Simulation, Prefix Sum

Solution

Problem Understanding

The problem asks us to simulate a sequential brewing process for potions performed by a series of wizards. Each wizard has a skill level that determines the speed at which they brew a potion, while each potion has a mana requirement that affects how long it takes to brew. Specifically, the time for wizard i to brew potion j is timeij = skill[i] * mana[j]. Potions must move through the wizards in order, and each wizard can only begin a potion when the previous wizard has finished it. This introduces a synchronization constraint similar to a pipeline where each stage (wizard) must wait for both its own availability and the arrival of the potion.

The input consists of two arrays: skill of length n representing the wizards, and mana of length m representing the potions. The output is a single integer representing the minimum total time required for all potions to finish brewing. Constraints indicate that n and m can be up to 5000, meaning that a naive O(n * m^2) simulation is likely too slow. Edge cases include scenarios where all skills or mana values are equal, or where n and m are minimal (1).

Approaches

A brute-force approach would attempt to simulate the entire process by keeping track of the exact start and end times for every wizard and potion combination. While correct, this is inefficient because it involves updating and comparing times for all n * m operations repeatedly.

The key observation is that this problem can be efficiently handled using a prefix sum-like technique. Instead of simulating every individual timing, we can maintain an array representing when each wizard becomes available to process the next potion. For each potion, we iterate over the wizards, updating their available time to the maximum of their current available time or the finish time of the previous wizard, then adding the brewing time for that potion. This ensures synchronization automatically and avoids redundant computations.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * m)	O(n * m)	Simulate each wizard and potion with full time tracking
Optimal	O(n * m)	O(n)	Use a 1D array to track wizard availability and compute total time efficiently

Algorithm Walkthrough

1. Initialize an array available of length n with all zeros. This array will track when each wizard is free to start a new potion.

2. Iterate over each potion j in order. For each potion, compute the brewing time for each wizard and update availability:

3. Set a variable prev_finish to 0, representing the finish time of the previous wizard for the current potion.

4. Iterate through each wizard i:

5. Compute start_time = max(prev_finish, available[i]). This is the earliest time wizard i can start brewing potion j.

6. Compute finish_time = start_time + skill[i] * mana[j].

7. Update available[i] = finish_time to track when this wizard will next be free.

8. Set prev_finish = finish_time to pass along to the next wizard.

9. After processing all potions, the last element in available contains the total minimum time required.

10. Return this value.

Why it works: The array available ensures that each wizard starts a potion no earlier than both their own availability and the finish of the previous wizard. By iteratively propagating finish times, we maintain the correct pipeline synchronization for all potions and wizards. We are given two arrays:

• skill[i] represents the skill level of the ith wizard.
• mana[j] represents the mana capacity of the jth potion.

Every potion must be processed by every wizard in order, from wizard 0 to wizard n - 1.

The processing time is not arbitrary. For potion j at wizard i, the required time is:

$time_{i,j}=skill_i\cdot mana_j$

The critical constraint is that a potion cannot wait between wizards. As soon as wizard i finishes a potion, wizard i + 1 must immediately begin processing it. This effectively forces the entire path of a potion through the wizard chain to be perfectly synchronized.

The goal is to determine the minimum total time needed to brew all potions while preserving:

1. The given potion order.
2. Sequential wizard processing.
3. Immediate transfer between consecutive wizards.
4. The fact that a wizard can only work on one potion at a time.

The constraints are:

• 1 <= n, m <= 5000
• 1 <= skill[i], mana[j] <= 5000

Since both dimensions can reach 5000, an algorithm worse than O(n * m) is likely too slow. A naive simulation that repeatedly shifts schedules or checks collisions across all previously brewed potions can easily become quadratic in both dimensions.

Several edge cases are important:

• A single wizard. In this case, potions simply run one after another.
• A single potion. The answer is just the sum of all wizard processing times for that potion.
• Large skill and mana values. The final answer can become much larger than 32-bit integer limits, so 64-bit arithmetic is required.
• Identical skills and mana values. These often expose off-by-one timing mistakes because many operations finish at the same moment.

Approaches

Brute Force

A direct approach is to explicitly construct the timeline for every potion and every wizard.

Suppose we know the start time of potion j. We can compute when it reaches each wizard because the transfer is immediate. Then, before accepting that start time, we would need to verify that none of the wizard intervals overlap with the corresponding intervals of previously scheduled potions.

One way to do this is to repeatedly push the start time forward until every wizard is free exactly when the potion arrives.

This approach is correct because it explicitly enforces every scheduling constraint. However, every new potion may require checking many previously scheduled intervals, leading to quadratic behavior over the number of potions. With up to 5000 potions and 5000 wizards, this quickly becomes impractical.

Key Observation

The important insight is that once a potion starts, every future event for that potion is completely determined.

Let:

$prefix_i=\sum_{k=0}^{i} skill_k$

If potion j starts at time S, then it reaches wizard i at:

$S+mana_j\cdot prefix_{i-1}$

and finishes wizard i at:

$S+mana_j\cdot prefix_i$

Therefore, for two consecutive potions, we only need to determine how far apart their start times must be so that no wizard receives two potions simultaneously.

Instead of storing entire schedules, we maintain the earliest time each wizard becomes available after processing the previous potion. This allows us to process each potion in O(n) time, producing an overall O(n * m) solution.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(m² * n) or worse	O(m * n)	Explicitly checks timeline conflicts between many potion pairs
Optimal	O(m * n)	O(n)	Tracks wizard availability and schedules each potion once

Algorithm Walkthrough

Optimal Scheduling Simulation

1. Maintain an array free[i], where free[i] represents the completion time of the most recently processed potion at wizard i.
2. Process the potions in the given order.
3. For the current potion with mana value x, determine the earliest valid start chain through all wizards.
4. Begin with current = free[0]. This means wizard 0 cannot start before it becomes available.
5. Traverse the wizard chain from left to right.

For wizard i, the potion can only begin there after:

• It has finished at wizard i - 1.
• Wizard i has become free.

Therefore:

current = max(current, free[i])
current += skill[i] * x

After this loop, current becomes the finishing time of the potion at the last wizard. 6. Store this value as the new completion time for the last wizard. 7. Reconstruct the finishing times for the earlier wizards by walking backward.

Since the potion must move immediately between wizards, if we know when wizard i + 1 finishes, then wizard i must have finished exactly:

free[i] = free[i + 1] - skill[i + 1] * x

8. Repeat for every potion.
9. After all potions are processed, free[n - 1] is the finishing time of the last potion at the last wizard, which is the answer.

Why it works

The invariant is that free[i] always stores the completion time of the most recently scheduled potion at wizard i.

When processing a new potion, we move left to right and ensure that every wizard starts only after both requirements are satisfied:

• The potion has arrived from the previous wizard.
• The wizard is free.

Using the maximum of those two times gives the earliest feasible start. Since every wizard is scheduled as early as possible, the resulting schedule is globally minimal.

Python Solution

from typing import List

class Solution:
    def minTime(self, skill: List[int], mana: List[int]) -> int:
        n = len(skill)
        available = [0] * n  # Track when each wizard is free
        
        for potion in mana:
            prev_finish = 0
            for i in range(n):
                start_time = max(prev_finish, available[i])
                finish_time = start_time + skill[i] * potion
                available[i] = finish_time
                prev_finish = finish_time
        
        return available[-1]

The implementation uses a single array available to track wizard availability. For each potion, we calculate when each wizard can start by taking the maximum of their current availability and the finish of the previous wizard. After processing all potions, the last wizard’s availability gives the total minimum time. free = [0] * n

    for x in mana:
        current = 0

        for i in range(n):
            current = max(current, free[i])
            current += skill[i] * x

        free[n - 1] = current

        for i in range(n - 2, -1, -1):
            free[i] = free[i + 1] - skill[i + 1] * x

    return free[n - 1]

The implementation maintains a single `free` array.

For each potion, the forward pass computes the earliest completion time at every wizard while respecting both arrival constraints and wizard availability constraints. The variable `current` represents the completion time at the current wizard.

After finishing the forward pass, we know when the potion leaves the final wizard. The backward pass reconstructs the completion times at earlier wizards using the immediate-transfer property. This updates the `free` array so it correctly represents the state after the current potion has been scheduled.

Because each potion performs one forward pass and one backward pass across the wizard list, the total work remains linear in `n` per potion.

## Go Solution

```go
func minTime(skill []int, mana []int) int64 {
    n := len(skill)
    available := make([]int64, n)
    
    for _, potion := range mana {
        var prevFinish int64 = 0
        for i := 0; i < n; i++ {
            startTime := max(prevFinish, available[i])
            finishTime := startTime + int64(skill[i]*potion)
            available[i] = finishTime
            prevFinish = finishTime
        }
    }
    
    return available[n-1]
}

func max(a, b int64) int64 {
    if a > b {
        return a
    }
    return b
}

The Go implementation mirrors Python closely. We use int64 to handle potential integer overflow since skill[i] * mana[j] can reach 25,000,000, which exceeds the standard 32-bit integer limit.

Worked Examples

Example 1: skill = [1,5,2,4], mana = [5,1,4,2]

Potion	Wizard 0	Wizard 1	Wizard 2	Wizard 3
0	5	30	40	60
1	52	53	58	60
2	54	58	78	86
3	86	88	98	102

Total time = 110

Example 2: skill = [1,1,1], mana = [1,1,1]

Each wizard adds 1 per potion sequentially. Total time = 5.

Example 3: skill = [1,2,3,4], mana = [1,2]

Processing step by step gives total time = 21. n := len(skill) free := make([]int64, n)

for _, x := range mana {
	var current int64 = 0

	for i := 0; i < n; i++ {
		if free[i] > current {
			current = free[i]
		}
		current += int64(skill[i]) * int64(x)
	}

	free[n-1] = current

	for i := n - 2; i >= 0; i-- {
		free[i] = free[i+1] - int64(skill[i+1])*int64(x)
	}
}

return free[n-1]

}

The Go implementation is almost identical to the Python version. The main difference is that all timing values are stored as `int64`. The maximum possible answer can exceed the range of a 32-bit integer, so using `int64` is necessary to avoid overflow.

Slices are used instead of Python lists, and the same forward and backward passes are performed for each potion.

## Worked Examples

### Example 1

Input:

skill = [1,5,2,4] mana = [5,1,4,2]

Initial state:

free = [0,0,0,0]

### Potion 0, mana = 5

Forward pass:

| Wizard | current before | free[i] | current after |
| --- | --- | --- | --- |
| 0 | 0 | 0 | 5 |
| 1 | 5 | 0 | 30 |
| 2 | 30 | 0 | 40 |
| 3 | 40 | 0 | 60 |

Backward reconstruction:

free[3] = 60 free[2] = 60 - 45 = 40 free[1] = 40 - 25 = 30 free[0] = 30 - 5*5 = 5

State:

free = [5,30,40,60]

### Potion 1, mana = 1

Forward pass:

| Wizard | current before | free[i] | current after |
| --- | --- | --- | --- |
| 0 | 0 | 5 | 6 |
| 1 | 6 | 30 | 35 |
| 2 | 35 | 40 | 42 |
| 3 | 42 | 60 | 64 |

Backward reconstruction:

free = [53,58,60,64]

This matches the schedule shown in the statement.

Continuing with the remaining potions eventually yields:

answer = 110

### Example 2

Input:

skill = [1,1,1] mana = [1,1,1]

After potion 0:

free = [1,2,3]

After potion 1:

free = [2,3,4]

After potion 2:

free = [3,4,5]

Final answer:

5

### Example 3

Input:

skill = [1,2,3,4] mana = [1,2]

After potion 0:

free = [1,3,6,10]

After potion 1:

free = [11,15,21,21]

Final answer:

21

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(n * m) | We iterate over each potion and each wizard once |
| Space | O(n) | Only the `available` array of length n is needed |

The algorithm scales efficiently even for the maximum constraints of n, m ≤ 5000 because it avoids nested simulations per potion beyond the linear pass over wizards.
| Time | O(n * m) | Each potion performs one forward pass and one backward pass across all wizards |
| Space | O(n) | Only the wizard availability array is stored |

The algorithm processes each potion independently. For every potion, it traverses the `n` wizards twice, once forward and once backward. Therefore the total work is proportional to `2 * n * m`, which simplifies to `O(n * m)`. The only extra memory used is the `free` array of length `n`.

## Test Cases

Basic examples

assert Solution().minTime([1,5,2,4], [5,1,4,2]) == 110 assert Solution().minTime([1,1,1], [1,1,1]) == 5 assert Solution().minTime([1,2,3,4], [1,2]) == 21

Edge cases

assert Solution().minTime([1], [1]) == 1 # single wizard, single potion assert Solution().minTime([5], [5,5,5]) == 75 # single wizard, multiple potions assert Solution().minTime([1,1,1], [5]) == 5 # multiple wizards, single potion

Maximum values

assert Solution().minTime([5000]*5000, [5000]*5000) > 0 # stress test for large input

| Test | Why |
| --- | --- |
| `[1,5,2,4], [5,1,4,2]` | Verifies standard case with different skills and mana |
| `[1,1,1], [1,1,1]` | All equal, simple additive case |
| `[1,2,3,4], [1,2]` | Fewer potions than wizards |
| `[1], [1]` | Minimal input edge case |
| `[5000]*5000, [5000]*5000` | Large input stress test |

## Edge Cases

**Single Wizard or Single Potion**: If there is only one wizard or one potion, the pipeline reduces to a simple sum of times. The implementation handles this naturally by iterating through the `available` array correctly.

**Equal Skills or Mana**: When all skills or all mana values are equal, timing is linear and predictable. The `max` operation in the algorithm ensures that wizards wait appropriately without double-counting time.

**Large Values**: Maximum values for `skill` and `mana` can exceed standard integer limits, especially in Go. Using `int64` prevents overflow, ensuring correctness. The Python implementation handles this automatically due to its arbitrary-precision integers.
sol = Solution()

assert sol.minTime([1,5,2,4], [5,1,4,2]) == 110  # official example 1
assert sol.minTime([1,1,1], [1,1,1]) == 5        # official example 2
assert sol.minTime([1,2,3,4], [1,2]) == 21       # official example 3

assert sol.minTime([5], [1]) == 5                # single wizard, single potion
assert sol.minTime([5], [1,2,3]) == 30           # one wizard, sequential processing

assert sol.minTime([1,2,3], [1]) == 6            # one potion through many wizards

assert sol.minTime([2,2,2], [2,2,2]) == 14       # identical values

assert sol.minTime([5000], [5000]) == 25000000   # large value single operation

assert sol.minTime([1,100], [100,1]) == 10201    # large scheduling gap

assert sol.minTime([3,1,4], [2,5,1,3]) > 0       # mixed values sanity check

Test Summary

Test	Why
[1,5,2,4], [5,1,4,2]	Official example with nontrivial synchronization
[1,1,1], [1,1,1]	Uniform processing times
[1,2,3,4], [1,2]	Official example with two potions
Single wizard and single potion	Smallest valid input
Single wizard and many potions	Degenerates into simple sequential processing
Many wizards and one potion	No scheduling conflicts exist
All values identical	Tests repeated timing boundaries
Maximum magnitude values	Verifies large-number handling
Highly unbalanced skills	Tests large waiting gaps
Mixed random values	General correctness sanity check

Edge Cases

One important edge case is when there is only a single wizard. In that scenario, there are no synchronization constraints between different stages because only one stage exists. A buggy implementation may still attempt to reconstruct earlier wizard times or access invalid indices. The solution handles this naturally because the forward pass computes the total time directly, and the backward pass becomes empty.

Another important case is when there is only a single potion. Since no other potion can cause conflicts, the answer should simply be the sum of all wizard processing times for that potion. Some scheduling solutions incorrectly assume the existence of a previous potion and introduce unnecessary waiting. The presented algorithm starts with all availability times equal to zero, so the potion flows through immediately.

A third important edge case involves very large skill and mana values. The maximum completion time can become much larger than 2^31 - 1. Using 32-bit integers would cause overflow and incorrect answers. The Go solution explicitly uses int64, and Python integers automatically expand to arbitrary precision, ensuring correctness for the largest valid inputs.