LeetCode Entry

3494. Find the Minimum Amount of Time to Brew Potions

09.10.2025 medium 2025 kotlin rust

Min total time to finish all skills[i] mana[j], non-intersecting

3494. Find the Minimum Amount of Time to Brew Potions medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1137

Problem TLDR

Min total time to finish all skills[i]*mana[j], non-intersecting #medium #bs

Intuition

The order is preserved. Binary Search the start time for each potion. Check if all next times are bigger then previous.

Approach

• use Long.MAX_VALUE / 2 for right border of bs
• n^2 solution from lee: optimal start(mana) = max_i(finish[i+1]-mana * sum(skills[0..i]))

Complexity

• Time complexity: \(O(n^2log(n))\)

• Space complexity: \(O(n)\)

Code

// 1681ms
    fun minTime(s: IntArray, m: IntArray): Long {
        val ts = LongArray(s.size + 1)
        for (p in m) {
            var lo = ts[0]; var hi = Long.MAX_VALUE / 2
            while (lo <= hi) {
                val m = (lo + hi)/2; var curr = m
                for (i in 1..<ts.size) {
                    if (curr < ts[i]) { curr = -1; break }
                    curr += s[i-1] * p
                }
                if (curr >= 0) hi = m - 1 else lo = m + 1
            }
            ts[0] = lo; for (i in 1..<ts.size) ts[i] = ts[i-1] + 1L * s[i-1] * p
        }
        return ts.last()
    }

// 53ms
    pub fn min_time(mut s: Vec<i32>, m: Vec<i32>) -> i64 {
        for i in 1..s.len() { s[i] += s[i - 1] }; let mut p = 0i64;
        (1..m.len()).map(|i|
            (1..s.len()).fold(s[0] as i64 * m[i - 1] as i64, |min, j|
                min.max(m[i-1] as i64 * s[j] as i64 - m[i] as i64 * s[j-1] as i64))
        ).sum::<i64>() + s[s.len()-1] as i64 * m[m.len()-1] as i64
    }