Find the Minimum Amount of Time to Brew Potions - Problem

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 i-th wizard on the j-th potion is time[i][j] = skill[i] * mana[j].

Important: Since the brewing process is delicate, a 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 all potions to be brewed properly.

Input & Output

Example 1 — Basic Case

$ Input: skill = [2,3,1], mana = [2,3]

› Output: 22

💡 Note: Potion 1 (mana=2): Wizard 0 finishes at time 4, Wizard 1 at max(0,4)+6=10, Wizard 2 at max(0,10)+2=12. Potion 2 (mana=3): Wizard 0 finishes at time 4+6=10, Wizard 1 at max(10,10)+9=19, Wizard 2 at max(12,19)+3=22. Final completion time is 22.

Example 2 — Single Wizard

$ Input: skill = [5], mana = [1,2,3]

› Output: 30

💡 Note: Single wizard processes potions sequentially: 5*1 + 5*2 + 5*3 = 5 + 10 + 15 = 30

Example 3 — Single Potion

$ Input: skill = [1,2,3], mana = [4]

› Output: 24

💡 Note: One potion through three wizards: Wizard 0 finishes at time 4, Wizard 1 at max(0,4)+8=12, Wizard 2 at max(0,12)+12=24. Total completion time is 24.

Constraints

1 ≤ n, m ≤ 10³
1 ≤ skill[i], mana[j] ≤ 10⁴

Visualization

Tap to expand

Asked in

G Google 25 a Amazon 20 M Microsoft 15

The key insight is that each wizard must wait for the previous wizard to finish before starting work on a potion. Best approach is simulation tracking each wizard's finish time. Time: O(n×m), Space: O(n)

Common Approaches

✓ Prefix Sum Optimization

⏱️ Time: O(n×m) Space: O(n)

Calculate prefix sums of skills to determine the minimum time more efficiently. This approach recognizes that the total time depends on both the sequential processing and the cumulative skill requirements.

Simulation Approach

⏱️ Time: O(n×m) Space: O(n)

Track when each wizard becomes available and calculate the exact time each potion finishes at each wizard. The last potion's completion time at the last wizard is the answer.

Prefix Sum Optimization — Algorithm Steps

Calculate prefix sums of skill array
For each potion, determine optimal timing using prefix sums
Track maximum completion time across all wizards
Return the final completion time

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate Prefix Sums

Precompute cumulative skill values for efficiency

Process with Optimization

Use prefix sums to determine optimal timing

Final Result

Minimum total brewing time

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

long long max(long long a, long long b) {
    return a > b ? a : b;
}

long long solution(int* skill, int skillSize, int* mana, int manaSize) {
    // Calculate prefix sums for optimization
    long long* prefixSkill = (long long*)calloc(skillSize + 1, sizeof(long long));
    for (int i = 0; i < skillSize; i++) {
        prefixSkill[i + 1] = prefixSkill[i] + skill[i];
    }
    
    long long* wizardFinishTime = (long long*)calloc(skillSize, sizeof(long long));
    
    for (int j = 0; j < manaSize; j++) {
        for (int i = 0; i < skillSize; i++) {
            long long processingTime = (long long)skill[i] * mana[j];
            if (i == 0) {
                wizardFinishTime[i] += processingTime;
            } else {
                wizardFinishTime[i] = max(wizardFinishTime[i], wizardFinishTime[i-1]) + processingTime;
            }
        }
    }
    
    long long result = wizardFinishTime[skillSize-1];
    free(prefixSkill);
    free(wizardFinishTime);
    return result;
}

int main() {
    char line[10000];
    int skill[1000], mana[1000];
    int skillSize = 0, manaSize = 0;
    
    // Parse skill array
    fgets(line, sizeof(line), stdin);
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (token[0] >= '0' && token[0] <= '9' || token[0] == '-') {
            skill[skillSize++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    // Parse mana array
    fgets(line, sizeof(line), stdin);
    token = strtok(line, "[,]");
    while (token != NULL) {
        if (token[0] >= '0' && token[0] <= '9' || token[0] == '-') {
            mana[manaSize++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    printf("%lld\n", solution(skill, skillSize, mana, manaSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n×m)

Still need to process each potion through each wizard, but with optimized calculations

✓ Linear Growth

Space Complexity

O(n)

Prefix sum array and wizard finish time tracking

⚡ Linearithmic Space

23.0K Views

Medium Frequency

~25 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Find the Minimum Amount of Time to Brew Potions - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Prefix Sum Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler