LeetCode in Kotlin

3469. Find Minimum Cost to Remove Array Elements

Medium

You are given an integer array nums. Your task is to remove all elements from the array by performing one of the following operations at each step until nums is empty:

Return the minimum cost required to remove all the elements.

Example 1:

Input: nums = [6,2,8,4]

Output: 12

Explanation:

Initially, nums = [6, 2, 8, 4].

The cost to remove all elements is 8 + 4 = 12. This is the minimum cost to remove all elements in nums. Hence, the output is 12.

Example 2:

Input: nums = [2,1,3,3]

Output: 5

Explanation:

Initially, nums = [2, 1, 3, 3].

The cost to remove all elements is 2 + 3 = 5. This is the minimum cost to remove all elements in nums. Hence, the output is 5.

Constraints:

Solution

import kotlin.math.max
import kotlin.math.min

class Solution {
    fun minCost(nums: IntArray): Int {
        var nums = nums
        var n = nums.size
        if (n % 2 == 0) {
            nums = nums.copyOf(++n)
        }
        val dp = IntArray(n)
        var j = 1
        while (j < n - 1) {
            var cost1: Int = INF
            var cost2: Int = INF
            val max = max(nums[j], nums[j + 1])
            for (i in 0..<j) {
                cost1 =
                    min(cost1, dp[i] + max(nums[i], nums[j + 1]))
                cost2 = min(cost2, dp[i] + max(nums[i], nums[j]))
                dp[i] += max
            }
            dp[j] = cost1
            dp[j + 1] = cost2
            j += 2
        }
        var result: Int = INF
        for (i in 0..<n) {
            result = min(result, dp[i] + nums[i])
        }
        return result
    }

    companion object {
        private const val INF = 1e9.toInt()
    }
}