LeetCode in Kotlin

4008. Minimum Initial Strength to Defeat All Monsters

Medium

You are given an integer array monsters, where monsters[i] represents the strength of the ith monster.

You are also given a 2D integer array boosts, where boosts[i] = [li, ri, vi] indicates that vi is added to your temporary bonus while fighting any monster whose index lies in [li, ri]. Boost ranges may overlap, and the values of all applicable boosts are added together.

You start with a non-negative initial strength and fight the monsters from left to right.

For each monster at index i:

Return the minimum initial strength required to defeat all monsters.

Note: The temporary bonus is used only to determine whether the current monster can be defeated. It does not otherwise change your current strength.

Example 1:

Input: monsters = [5,10,15], boosts = [[1,1,10]]

Output: 30

Explanation:

Let’s start with an initial strength of 30.

Thus, the minimum initial strength required is 30.

Example 2:

Input: monsters = [5,10,15], boosts = [[1,2,10],[1,2,5]]

Output: 5

Explanation:

Let’s start with an initial strength of 5.

Thus, the minimum initial strength required is 5.

Constraints:

Solution

import kotlin.math.max

class Solution {
    fun minInitialStrength(monsters: IntArray, boosts: Array<IntArray>): Long {
        val n = monsters.size
        val diff = LongArray(n)
        for (boost in boosts) {
            val l = boost[0]
            val r = boost[1]
            val v = boost[2]
            diff[r] += v.toLong()
            if (l > 0) {
                diff[l - 1] -= v.toLong()
            }
        }
        var res: Long = 0
        var bonus: Long = 0
        for (i in n - 1 downTo 0) {
            bonus += diff[i]
            if (res > 0) {
                res += monsters[i].toLong()
            } else {
                res = max(0L, monsters[i] - bonus)
            }
        }
        return res
    }
}